很久没写线段树了，没想到这两场比赛都遇到了线段树的题目。看来是有必要重新复习一下了。。。。。 对于这道题的话其实就是线段树，，我们只需要维护一下区间的最小值和最大值就可以应对题目的问题了。
代码如下：
;a[maxn],_max,_min,lazy[maxn*4];int minv[maxn*4],maxv[maxn*4];void maintain(int o,int L,int R){int lc=2*o,rc=2*o+1;minv[o]=min(minv[lc],minv[rc]);maxv[o]=max(maxv[lc],maxv[rc]);}void pushdown(int o,int L,int R){int lc=2*o,rc=2*o+1,M=(R+L)/2;if(lazy[o]!=INF){minv[lc]+=lazy[o];maxv[lc]+=lazy[o];minv[rc]+=lazy[o];maxv[rc]+=lazy[o];if(lazy[lc]==INF)lazy[lc]=lazy[o];elselazy[lc]+=lazy[o];if(lazy[rc]==INF)lazy[rc]=lazy[o];elselazy[rc]+=lazy[o];lazy[o]=INF;}}void update(int o,int L,int R,int ql,int qr,int v){int M=L+(R-L)/2;if(ql<=L&&qr>=R){minv[o]+=v;maxv[o]+=v;if(lazy[o]==INF)lazy[o]=v;elselazy[o]+=v;return ;}pushdown(o,L,R);if(ql<=M)update(o*2,L,M,ql,qr,v);if(qr>M)update(o*2+1,M+1,R,ql,qr,v);maintain(o,L,R);}void query(int o,int L,int R,int ql,int qr){int M=L+(R-L)/2;if(ql<=L&&qr>=R){_max=max(_max,maxv[o]);_min=min(_min,minv[o]);return ;}pushdown(o,L,R);if(ql<=M)query(o*2,L,M,ql,qr);if(qr>M)query(2*o+1,M+1,R,ql,qr);}void Init(){_max=0; _min=INF;}int main(){int n,top,Q;while(scanf(“%d%d%d”,&n,&top,&Q)!=EOF){memset(lazy,0x3f,sizeof(lazy));memset(maxv,0,sizeof(maxv));memset(minv,0,sizeof(minv));while(Q–){char str[100];int A,B,S;scanf(“%s”,str);if(str[0]==’s’) ///state{scanf(“%d”,&A);A++;Init();query(1,1,n,A,A);printf(“%d\n”,_min);}if(str[0]==’g’) ///group change{scanf(“%d%d%d”,&A,&B,&S);A++;B++;Init();query(1,1,n,A,B);if(S<=0){if(S+_min<0){int t=_min*-1;update(1,1,n,A,B,t);printf(“%d\n”,t);}else{update(1,1,n,A,B,S);printf(“%d\n”,S);}}else{if(_max+S>top){int t=top-_max;update(1,1,n,A,B,t);printf(“%d\n”,t);}else{update(1,1,n,A,B,S);printf(“%d\n”,S);}}}if(str[0]==’c’) ///change{scanf(“%d%d”,&A,&S);A++;Init();query(1,1,n,A,A);if(S<=0){if(S+_min<0){int t=-1*_min;update(1,1,n,A,A,t);printf(“%d\n”,t);}else{update(1,1,n,A,A,S);printf(“%d\n”,S);}}else{if(S+_max>top){int t=top-_max;update(1,1,n,A,A,t);printf(“%d\n”,t);}else{update(1,1,n,A,A,S);printf(“%d\n”,S);}}}}} return 0;}
坚韧是成功的一大要素，只要在门上敲得够久够大声，终会把人唤醒的。
