Cod sursa(job #188495)

Utilizator c_iulyanCretu Iulian c_iulyan Data 8 mai 2008 18:51:05
Problema Arbori de intervale Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
long n,m,a[100005],t[300000],x,y;

void make(int i,int j,int nd)
{
if(i==j) t[nd]=a[i];
else
   {
   long m=(i+j)/2;
   make(i,m,nd*2);
   make(m+1,j,nd*2+1);
   t[nd]=max(t[nd*2],t[nd*2+1]);
   }
}

void upd(long i,long j,long nd)
{
if(i==j)
   {
   t[nd]=y;
   return;
   }

long m=(i+j)/2;

if(x<=m)
   upd(i,m,nd*2);
else
   upd(m+1,j,nd*2+1);
   
t[nd]=max(t[nd*2],t[nd*2+1]);
}

long long ask(long i,long j,long nd)
{
if(x<=i&&j<=y)
   return t[nd];
   
long long m=(i+j)/2,s1=0,s2=0;

if(x<=m)
   s1=ask(i,m,nd*2);
if(m<y)
   s2=ask(m+1,j,nd*2+1);

return max(s1,s2);
}

void rd()
{
scanf("%ld%ld",&n,&m);
long i;
for(i=1;i<=n;i++)
   scanf("%ld",&a[i]);

make(1,n,1);
int p;

for(i=1;i<=m;i++)
   {
   scanf("%d%ld%ld",&p,&x,&y);
   if(p==1) upd(1,n,1);
   else printf("%lld\n",ask(1,n,1));
   }
}

int main()
{
freopen("arbint.in","r",stdin);
freopen("arbint.out","w",stdout);

rd();

return 0;
}