Cod sursa(job #699340)

Utilizator arch_enemyAngela Gossow arch_enemy Data 29 februarie 2012 18:56:17
Problema Arbori de intervale Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <cstdio>
#include <cstring>

#define NMAX 100001
#define LMAX 300000
#define max(a,b) (a>b) ? (a) : (b)

int N, Q, Tip, A, B, i;
int AI[LMAX], Val[NMAX];

inline void Build( int Nod, int St, int Dr )
{
	if( St == Dr )
	{
		AI[Nod] = Val[St];
		return;
	}
	
	int M = St + ((Dr-St)>>1);
	Build( (Nod<<1), St, M );
	Build( ((Nod<<1)|1), M + 1, Dr );
	
	AI[Nod] = max( AI[(Nod<<1)], AI[((Nod<<1)|1)] );
}

inline void Update( int Nod, int St, int Dr, int Pos, int Val )
{
	if( St == Dr )
	{
		AI[Nod] = Val;
		return;
	}
	
	int M = St + ((Dr-St)>>1);
	if( Pos <= M )
		Update( (Nod<<1), St, M, Pos, Val );
	else 
		Update( ((Nod<<1)|1), M + 1, Dr, Pos, Val );
	
	AI[Nod] = max( AI[(Nod<<1)], AI[((Nod<<1)|1)] );
}

inline int Query( int Nod, int St, int Dr, int StQ, int DrQ )
{
	if( StQ <= St && Dr <= DrQ )
		return AI[Nod];
	
	int M = St + ((Dr-St)>>1);
	
	int Rez = 0;
	if( StQ <= M )
		Rez = Query( (Nod<<1), St, M, StQ, DrQ );
	if( DrQ > M )
		Rez = max( Rez, Query( ((Nod<<1)|1), M + 1, Dr, StQ, DrQ ) );
	
	return Rez;
}

int main()
{
	freopen("arbint.in", "r", stdin);
	freopen("arbint.out", "w", stdout);
	
	scanf("%d%d", &N, &Q );
	memset( AI, 0, sizeof(AI) );
	for( i = 1; i <= N; ++i )
		scanf("%d", &Val[i] );
	Build( 1, 1, N );
	
	for( ; Q--; )
	{
		scanf("%d%d%d", &Tip, &A, &B );
		if( !Tip )
			printf("%d\n", Query( 1, 1, N, A, B ) );
		else
			Update( 1, 1, N, A, B );
	}
	
	return 0;
}