题意：有N个学生M条操作，0<N<=200000，0<M<5000，要么查询某区间内学生的最高分，要么更改某学生的成绩。
分析：原理和线段树点修改求和类似。
#include<cstdio>
#include<map>
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 200000 + 10;
int a[MAXN];
int ma[MAXN << 2];
void build(int id, int L, int R){
if(L == R){
ma[id] = a[L];
}
else{
int mid = L + (R - L) / 2;
build(id << 1, L, mid);
build(id << 1 | 1, mid + 1, R);
ma[id] = max(ma[id << 1], ma[id << 1 | 1]);
}
}
void update(int pos, int id, int L, int R, int value){
if(L == R){
ma[id] = value;
}
else{
int mid = L + (R - L) / 2;
if(pos <= mid) update(pos, id << 1, L, mid, value);
else update(pos, id << 1 | 1, mid + 1, R, value);
ma[id] = max(ma[id << 1], ma[id << 1 | 1]);
}
}
int query(int l, int r, int id, int L, int R){
if(l <= L && R <= r){
return ma[id];
}
int ans = 0;
int mid = L + (R - L) / 2;
if(l <= mid) ans = max(ans, query(l, r, id << 1, L, mid));
if(r > mid) ans = max(ans, query(l, r, id << 1 | 1, mid + 1, R));
return ans;
}
int main(){
int N, M;
while(scanf("%d%d", &N, &M) == 2){
memset(a, 0, sizeof a);
memset(ma, 0, sizeof ma);
for(int i = 1; i <= N; ++i){
scanf("%d", &a[i]);
}
build(1, 1, N);
while(M--){
getchar();
char c;
scanf("%c", &c);
int x, y;
scanf("%d%d", &x, &y);
if(c == 'Q'){
printf("%d\n", query(x, y, 1, 1, N));
}
else if(c == 'U'){
update(x, 1, 1, N, y);
}
}
}
return 0;
}