Pagini recente » Borderou de evaluare (job #1953911) | Cod sursa (job #3184357)
#include <iostream>
using namespace std;
int n, m, val, poz, maxi, start, fin;
int arb_max[100005];
int maxim(int a, int b){
if(a < b){
return b;
}
return a;
}
void Update(int nod, int st, int dr){
if(st == dr){
arb_max[nod] = val;
return;
}
int mij = (dr + st) / 2;
if(poz <= mij){
Update(2*nod, st, mij);
}
else{
Update(2*nod + 1, mij + 1, dr);
}
arb_max[nod] = maxim(arb_max[2*nod], arb_max[2*nod + 1]);
}
void Query(int nod, int st, int dr){
if(start <= st && dr <= fin){
if(maxi < arb_max[nod])
maxi = arb_max[nod];
return;
}
int mij = (st + dr) / 2;
if(start <= mij)
Query(2*nod, st, mij);
if(mij < fin)
Query(2*nod+1, mij + 1, dr);
}
int main()
{
freopen("arbint.in", "r", stdin);
freopen("arbint.out", "w", stdout);
scanf("%d %d", &n, &m);
int i, x;
for(i = 1; i <= n; i++){
scanf("%d", &x);
poz = i;
val = x;
Update(1, 1, n);
// for(int j = 1; j <= n; j++){
// cout<<arb_max[j]<<' ';
// }
// cout<<endl;
}
for(i = 1; i<= m; i++){
int q, a, b;
scanf("%d %d %d", &q, &a, &b);
if(q == 0){
start = a;
fin = b;
maxi = -1;
Query(1, 1, n);
printf("%d\n", maxi);
}
if(q == 1){
poz = a;
val = b;
Update(1, 1, n);
}
}
return 0;
}