Cod sursa(job #718300)

Utilizator ILDottoreBogdan Stoian ILDottore Data 20 martie 2012 17:51:31
Problema Arbori de intervale Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<cstdio>
#include<algorithm>
using namespace std;

FILE *f=fopen("arbint.in","r");
FILE *g=fopen("arbint.out","w");

#define NMAX 100100
long n,m,arb[4*NMAX],maxim;

void update(long poz, long val,long st, long dr,long nod)
{
	if (st==dr)
	 { arb[nod]=val;
		return;
	 }
	 
	long mij=(st+dr)/2;
	
	if ( poz<= mij )  update(poz,val,st,mij,2*nod);
	else update(poz,val,mij+1,dr,2*nod+1);
	
	arb[nod]=max( arb[2*nod] , arb[2*nod+1] );
}


void query(long a,long b, long st,long dr,long nod)
{ 
	
	if (a<=st&&b>=dr)
	{  
	   if (arb[nod]>maxim) maxim=arb[nod];
	   return;
	}
long mij=(st+dr)/2;

if (a<=mij) query(a,b,st,mij,2*nod);
if (mij<b) query(a,b,mij+1,dr,2*nod+1);

}
	
	
	
int main()
{   
	fscanf(f,"%ld%ld",&n,&m);
	
	for (long i=1;i<=n;i++)
	{ 	long x;
		fscanf(f,"%ld",&x);
		update(i,x,1,n,1);
	}
	
	for (long i=1;i<=m;i++)
	{ int op; long x,y;
	fscanf(f,"%d",&op);
	
	fscanf(f,"%ld %ld",&y,&x);
	if (op)
	  update (y,x,1,n,1);
	else 
	  {maxim=-1;
	   query(y,x,1,n,1);
	   fprintf(g,"%ld\n",maxim);
	  }
	}
	
return 0;}