建树+单点更新+区间查询
第一次提交tle
第二次ole，先贴代码再分析
ac代码如下
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> int grade[200005]; int tree[800020]; int maxn(int i,int j) { if(i>j) return i; else return j; } void build(int p,int l,int r) { if(l==r){ tree[p]=grade[l]; return; } int mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r); tree[p]=maxn(tree[p*2],tree[p*2+1]); } void change(int p,int l,int r,int x,int num) { if(l==r) { tree[p]=num;return; } int mid=(l+r)/2; if(x<=mid) change(p*2,l,mid,x,num); else change(p*2+1,mid+1,r,x,num); tree[p]=maxn(tree[p*2],tree[p*2+1]); } int find(int p,int l,int r,int a,int b) { if(a<=l&&r<=b) return tree[p]; int mid=(l+r)/2; if(b<=mid) return find(p*2,l,mid,a,b); else if(a>mid) return find(p*2+1,mid+1,r,a,b); return maxn((find(p*2,l,mid,a,mid)),(find(p*2+1,mid+1,r,mid+1,b))); } int main() { int i,n,m,a,b; char c[2]; while(scanf("%d %d",&n,&m)!=EOF){ for(i=1;i<=n;i++) scanf("%d",&grade[i]); build(1,1,n); while(m--){ scanf("%s%d%d",c,&a,&b); if(c[0]=='Q') printf("%d ",find(1,1,n,a,b)); else if(c[0]=='U') change(1,1,n,a,b); } } return 0; }
第一次tle是因为对scanf理解还不够深，
几个例子分析一下：
scanf("%c",&c); printf("%c ",c)
输入a,回车的话，输出的结果为a，然后空两行。
char c[2]; scanf("%s",c); printf("%c",c[0]);
这样的话输入为a,输出为a。
scanf("%c",&c); getchar(); printf("%c",c);
这样的话和第二个相同，输入为a, 输出为a。
scanf在读入字符时会读入 ，中间可以插入一行getchar();消除 影响。
如果是读入字符串时，第二次的读入是从第一个非空白字符读入，非空白字符有空格、制表符、换行符，于是 被省略掉了，不会有影响。
第二次ole也是scanf的问题，
scanf的返回值取决于读入的数量，若都未被读入，则返回值为0，若出错或遇到end of line则返回-1，也就是EOF
直接写while(scanf("%d%d",&a,&b))的话，遇到EOF，返回值为-1而非0，则不会停止，陷入死循环，所以ole
忘记加!=EOF了orz
正确写法：
while(scanf()!=EOF)
while(~scanf())
诸如此类……