# Cod sursa(job #2107157)

Utilizator Data 16 ianuarie 2018 20:09:55 Arbori de intervale 40 cpp done Arhiva educationala 1.51 kb
``````#include <iostream>
#include <fstream>

using namespace std;
int maxArb[40020];
int pos,val,maxim = -1;
ifstream fin("arbint.in");
ofstream fout("arbint.out");

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

void update(int nod, int left, int right, int mponta)
{
if(left==right)
{
maxArb[nod]=mponta;
return;
}

int mid=(left+right)/2;
if ( pos <= mid )
update(2*nod,left,mid,mponta);
else
update(2*nod+1,mid+1,right,mponta);

maxArb[nod] = Maxim( maxArb[2*nod], maxArb[2*nod+1] );

}

void query(int nod, int left, int right, int start, int finish)
{

if(left >= start && right <= finish){
if(maxArb[nod]>maxim){
maxim = maxArb[nod];
}
return;
}
else{
if(left==right)
return;
int mid=(left+right)/2;
if(start<=mid)
query(2*nod,left,mid,start,finish);
if(mid<=finish)
query(2*nod+1,mid+1,right,start,finish);

}

}

int main()
{
int n,m,i,val,q,a,b,x;

fin >> n >> m;
for(i=1;i<=n;++i){
fin >> x;
val=x;
pos = i;
update(1,1,n,x);
}

for(i=1;i<=m;++i){
fin>>q>>a>>b;
if(q==1){
pos = a; val = b;
update(1,1,n,b);
}
else{
query(1,1,n,a,b);
fout << maxim << "\n";
maxim=-1;
}
}

return 0;
}
``````