学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
Output 对于每一次询问操作，在一行里面输出最高成绩。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
HintHuge input,the C function scanf() will work better than cin
AC代码：
#include
#include
using namespace std; int n,m; struct tree { int l,r,key; } node[600000]; int score[600000]; int X,Y; int max(int x,int y) { return x>y?x:y; } int build(int l,int r,int i) //建树 { int mid=(l+r)/2; node[i].l=l; node[i].r=r; if(l==r) { node[i].key=score[l]; return node[i].key; } else { node[i].key=max(build(l,mid,2*i),build(mid+1,r,2*i+1)); //子节点中的最大值给父亲。 return node[i].key; } } void update(int i,int x,int key) { node[i].key=max(node[i].key,key); int mid=(node[i].l+node[i].r)/2; if(node[i].l==node[i].r) return ; if(x>mid) update(2*i+1,x,key); //x>mid往右边的节点找 else update(2*i,x,key); } int Quetion(int i,int l,int r) { if(node[i].l==l&&node[i].r==r) return node[i].key; else { int mid=(node[i].l+node[i].r)/2; if(l<=mid&&r>=mid+1) { return max(Quetion(2*i,l,mid),Quetion(2*i+1,mid+1,r)); } else if(l>=mid+1) { return Quetion(2*i+1,l,r); } else { return Quetion(2*i,l,r); } } } int main() { char ch; int a,b; while(scanf(%d %d,&n,&m)!=EOF) { int i; for(i=1; i<=n; i++) scanf(%d,&score[i]); build(1,n,1); while(m--) { getchar(); scanf(%c %d %d,&ch,&a,&b); if(ch=='U') update(1,a,b); else printf(%d ,Quetion(1,a,b)); } } return 0; }
?