5659
Hint
Huge input,the C function scanf() will work better than cin
线段树入门 ，第一次学线段树2015,7,28
#include<stdio.h>#include<algorithm>#include<string.h>//#define max(a,b) ((a) > (b)? (a):(b))//max这样定义会超时，这么定义居然比库函数慢这么多 using namespace std;#define M 200010struct node{int l,r,val;//val表示该区间的最大值 }s[M*3];//数组要开大点来存左右子树 void build(int root,int lc,int rc){s[root].l=lc; s[root].r=rc;if(lc==rc){scanf("%d",&s[root].val);//左右重合时 return;}int mid=(lc+rc)>>1; build(root<<1,lc,mid);build(root<<1|1,mid+1,rc);s[root].val=max(s[root<<1].val,s[root<<1|1].val);//回溯时更新val的值 } void update(int root,int lc,int rc,int v){if(s[root].l==lc && s[root].r==rc){s[root].val=v;//如果 return;}int mid=(s[root].l+s[root].r)>>1;if(rc<=mid){//更新左子树 update(root<<1,lc,rc,v);}else if(lc>mid){//右子树 update(root<<1|1,lc,rc,v);}else{update(root<<1,lc,mid,v);update(root<<1|1,mid+1,rc,v);}s[root].val=max(s[root<<1].val,s[root<<1|1].val); }int query(int u,int lc,int rc){if(s[u].l==lc && s[u].r==rc)return s[u].val;int mid=(s[u].l+s[u].r)>>1;if(rc<=mid)return query(u<<1,lc,rc);else if(lc>mid)return query(u<<1|1,lc,rc);elsereturn max(query(u<<1,lc,mid),query(u<<1|1,mid+1,rc));}int main(){int n,m,c,b;char ch;while(~scanf("%d%d",&n,&m)){ build(1,1,n); while(m–){getchar();scanf("%c%d%d",&ch,&c,&b);if(ch=='Q'){printf("%d\n",query(1,c,b));}else{update(1,c,c,b);} }}return 0;}/*还可以用树状数组来写这道题，树状数组相对于线段树代码简单，，但是树状数组的局限性比较大用线段树可以解决的问题用树状数组不一定能解决，能用树状数组的题，就一定可以用线段树解决，一半树状数组存放的是一个区间的和，这里存的是一段区间的最大值*/#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define M 200010int a[M],s[M];//a[]是原数组,s[]是树状数组 int n,m;int lowbit(int x){return x&(-x);//移位函数 }void change(int i,int num)//更新每个树状数组 {a[i]=num;while(i<=n){s[i]=max(s[i],num);i+=lowbit(i); }}int query(int l,int r)//查询找出最大值 {int ans=a[r];while(l!=r){r–;while(r-lowbit(r)>=l){ans=max(s[r],ans);r-=lowbit(r);}ans=max(ans,a[r]);}return ans;}int main(){int x,y,i;char ch;while(~scanf("%d%d",&n,&m)){memset(s,0,sizeof(s));//这一定要清0 for(i=1;i<=n;i++){scanf("%d",&a[i]);change(i,a[i]);}while(m–){getchar();scanf("%c%d%d",&ch,&x,&y);if(ch=='U'){change(x,y);}else{printf("%d\n",query(x,y));}}}return 0;}
接受失败也等于给了自己从零开始的机会，接受失败更是一种智者的宣言和呐喊;
