# Cod sursa(job #156345)

Utilizator Data 12 martie 2008 14:45:47 Arbori de intervale 50 cpp done Arhiva educationala 1.89 kb
``````#include <stdio.h>
#include <fstream>
using namespace std;

#define in "arbint.in"
#define out "arbint.out"
#define dim 100001

inline int Maxim(int a, int b) {
if ( a > b ) return a;
return b;
}

int N, M, X, Y, tip, size, K;
int Arb[dim], A[dim];
int St[dim], Dr[dim];

void Update();
int Query();

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

scanf("%d%d", &N, &M);
for ( int i = 1; i <= N; i++ )
scanf("%d", &A[i]);

size=0;
while ( size*size <= N ) size++;
size--;

K = N/size+1;

for ( int i = 1; i*size <= N; i++ )
{
Arb[i] = -1;
St[i] = size*(i-1)+1, Dr[i] = size*i;
for ( int nod = St[i]; nod <= Dr[i]; nod++ )
Arb[i] = Maxim(Arb[i],A[nod]);
}

for ( ; M; M-- )
{
scanf("%d%d%d", &tip, &X, &Y);

if ( tip ) Update();
else       printf("%d\n", Query());
}
}

void Update()
{
A[X] = Y;
for ( int i = 1; i*size <= N; i++ )
if ( X >= size*(i-1)+1 && X <= size*i )
{
Arb[i] = -1;
for ( int nod = size*(i-1)+1; nod <= size*i; nod++ )
Arb[i] = Maxim(Arb[i],A[nod]);

break;
}
}

int Query()
{
int maxim = -1;
int st = (1<<30), dr=-1;

for ( int i = 1; i <= K; i++ )
{
if ( X <= St[i] && Dr[i] <= Y )
{
if ( St[i] < st )  st = St[i];
if ( Dr[i] > dr )  dr = Dr[i];
maxim = Maxim(maxim,Arb[i]);
}
if ( Dr[i] > Y ) break;
}

if ( st == (1<<30) && dr == -1 ) st = dr = Y;

for ( int i = X; i <= st; i++ )
maxim = Maxim(maxim,A[i]);

for ( int i = dr; i <= Y; i++ )
maxim = Maxim(maxim,A[i]);

return maxim;
}
``````