题目大意
给定一个长度为n的序列，可以对其进行一下两种操作：
1、a L R V 把区间[L,R]的所有数增加V
2、q L R 查询区间[L,R]的最长连续上升子序列
题解
和HDU3308差不多，不过这里是区间更新，而前者是单点更新，增加一个add域，表示区间累加值，然后还需要增加两个域，节点的左端点值lval和右端点值rval，处理和HDU3308基本一样
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 100005 #define lson l,m,s<<1 #define rson m+1,r,s<<1|1 int msum[MAXN<<2],lsum[MAXN<<2],rsum[MAXN<<2],setv[MAXN<<2],lval[MAXN<<2],rval[MAXN<<2]; void PushUp(int s,int m) { lsum[s]=lsum[s<<1],rsum[s]=rsum[s<<1|1]; lval[s]=lval[s<<1],rval[s]=rval[s<<1|1]; msum[s]=max(msum[s<<1],msum[s<<1|1]); if(rval[s<<1]<lval[s<<1|1]) { if(lsum[s<<1]==(m-(m>>1))) lsum[s]+=lsum[s<<1|1]; if(rsum[s<<1|1]==(m>>1)) rsum[s]+=rsum[s<<1]; msum[s]=max(msum[s],rsum[s<<1]+lsum[s<<1|1]); } } void PushDown(int s) { if(setv[s]) { setv[s<<1]+=setv[s],setv[s<<1|1]+=setv[s]; lval[s<<1]+=setv[s],rval[s<<1]+=setv[s]; lval[s<<1|1]+=setv[s],rval[s<<1|1]+=setv[s]; setv[s]=0; } } void build(int l,int r,int s) { setv[s]=0; if(l==r) { scanf("%d",&lval[s]); rval[s]=lval[s]; msum[s]=lsum[s]=rsum[s]=1; return; } int m=(l+r)>>1; build(lson); build(rson); PushUp(s,r-l+1); } void update(int ql,int qr,int d,int l,int r,int s) { if(ql<=l&&r<=qr) { setv[s]+=d; lval[s]+=d; rval[s]+=d; return; } PushDown(s); int m=(l+r)>>1; if(ql<=m) update(ql,qr,d,lson); if(qr>m) update(ql,qr,d,rson); PushUp(s,r-l+1); } int query(int ql,int qr,int l,int r,int s) { if(ql<=l&&r<=qr) return msum[s]; PushDown(s); int m=(l+r)>>1,ans=0; if(ql<=m) ans=max(ans,query(ql,qr,lson)); if(qr>m) ans=max(ans,query(ql,qr,rson)); if(rval[s<<1]<lval[s<<1|1]) ans=max(ans,min(qr,m+lsum[s<<1|1])-max(ql,m-rsum[s<<1]+1)+1); return ans; } int main(void) { int T,n,m,x,y,v,p=0; char op[5]; scanf("%d",&T); while(T--) { printf("Case #%d:\n",++p); scanf("%d%d",&n,&m); build(1,n,1); while(m--) { scanf("%s",op); if(op[0]=='a') { scanf("%d%d%d",&x,&y,&v); update(x,y,v,1,n,1); } else { scanf("%d%d",&x,&y); printf("%d\n",query(x,y,1,n,1)); } } } return 0; }