题意：n个学生有初始成绩，，现在有m个操作，（Q,a,b）：询问区间学号为[a,b]的学生的最好成绩；（U,a,b）：修改学号为a的学生的成绩为b，要你执行这m项操作。
分析：
单点更新，区间查询。确切的说是单点替换，区间查询。线段的典型用法之二。
代码：
#include<iostream>#include<cstdio>#include<algorithm> using namespace std;const int maxn=200000;int n,m;int mx[maxn*4+10];void pushup(int rt){mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);}void creat(int l,int r,int rt){if(l==r){ // l==r 叶子节点，表示具体的某个学生//mx[rt]=0; //如果先建树再用upd更新初始值那么要在这里先赋初值，不然程序pushup()操作会出问题。赋任意值都行，因为输入初始值的时候会更新的 scanf("%d",&mx[rt]); //在这里建树的时候直接初始化也行 return;}int mid=(l+r)>>1; creat(l,mid,rt<<1);creat(mid+1,r,rt<<1|1);pushup(rt);}void upd(int a,int x,int l,int r,int rt){if(l==r){ //叶子节点，如果找到了学生a，那么更新他的成绩mx[rt]=x;return;}int mid=(l+r)>>1; if(a<=mid) upd(a,x,l,mid,rt<<1); //如果a在左区间，就去左区间找到他，然后更新他的成绩else upd(a,x,mid+1,r,rt<<1|1);//如果在右区间，就去右区间找他pushup(rt);//找到学生a更新他的成绩后要向上更新区间的最大值}int query(int a,int b,int l,int r,int rt){if(a<=l&&b>=r) return mx[rt]; //如果查询区间包含当前区间，那么直接返回区间最大值int mid=(l+r)>>1;//不然就在当前区间的左子区间找最大值，右子区间找最大值然后返回左右的最大值int ret=0;if(a<=mid)ret=max(ret,query(a,b,l,mid,rt<<1));if(b>mid) ret=max(ret,query(a,b,mid+1,r,rt<<1|1));return ret; } int main(){while(scanf("%d%d",&n,&m)!=EOF){creat(1,n,1);//for(int i=1;i<=n;i++){ //先建树再用更新操作更新初始值也可以，不过得在建树的时候先赋初值 //int a;//scanf("%d",&a);//upd(i,a,1,n,1);//}while(m–){char a[10];int b,c;scanf("%s%d%d",&a,&b,&c); //不能用%c，因为%c是不过滤空格和换行符的if(a[0]=='Q') printf("%d\n",query(b,c,1,n,1));else upd(b,c,1,n,1);}}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
忘掉失败，不过要牢记失败中的教训。
