2:43 AM
Sayef Azad Sakin
#define mx 1000010
#define tmx 2000020
int a[mx];
int t[tmx];
void init(int node, int i, int j){
if(i==j){
t[node] = a[i];
return;
}
int mid = (i+j)>> 1;
init(2*node, i, mid);
init((2*node)+1, mid+1, j);
t[node] = max(t[2*node], t[(2*node)+1]);
}
int query(int node, int i, int j, int si, int sj){
if(i == si && j == sj)return t[node];
int mid = (i+j)>> 1;
if(sj <= mid)return query(2*node, i, mid, si, sj);
else if(si > mid)return query((2*node)+1, mid+1, j, si, sj);
else{
int r1 = query(2*node, i, mid, si, mid);
int r2 = query((2*node)+1, mid+1, j, mid+1, sj);
return max(r1,r2);
}
}
void update(int node, int i, int j, int idx, int val){
if(i == j){
a[i] = val;
t[node] = val;
return;
}
int mid = (i+j)>> 1;
if(idx <= mid) update(2*node, i, mid, idx, val);
else update ((2*node)+1, mid+1, j, idx, val);
t[node] = max(t[2*node], t[(2*node)+1]);
}