Cod sursa(job #519479)
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int NMAX = 100000;
const int ARBMAX = 2*NMAX + 10;
int arb[4*NMAX + 10];
int pos, newValue;
void insert(int nod, int left, int right) {
if (left != right) {
int mid = (left + right)>>1;
if (pos <= mid) insert(nod<<1, left, mid);
else insert((nod<<1) + 1, mid + 1, right);
arb[nod] = max(arb[(nod<<1)], arb[(nod<<1)+1]);
} else arb[nod] = newValue;
}
int a, b, maxim;
void query(int nod, int left, int right) {
if (a>right || b<left) return; // minvalue
if (a<=left && b>=right) {
maxim = max(arb[nod], maxim);
return;
}
else {
int mid = (left + right)>>1;
if (mid >= left) query(nod<<1, left, mid);
if (mid+1 <= right) query((nod<<1) + 1, mid +1, right);
}
}
int main() {
freopen("arbint.in","r",stdin);
freopen("arbint.out","w",stdout);
int n, m;
scanf("%d%d", &n, &m);
for (int i=0; i<n; i++) {
int x;
scanf("%d", &x);
pos = i; newValue = x;
insert(1, 0, n-1);
}
for (int i=0; i<m; i++) {
int op, aa, bb;
scanf("%d%d%d", &op, &aa, &bb);
switch (op) {
case 0:
a=aa-1; b=bb-1;
maxim = 0;
query(1, 0, n-1);
printf("%d\n", maxim);
break;
case 1:
pos = aa-1; newValue = bb;
insert(1, 0, n-1);
break;
}
}
return 0;
}