题目地址：http://acm.uestc.edu.cn/problem.php?pid=1425
题目分析：题目中给出N个数的一个序列S={S1,S2, ... ,SN}。又在这个序列上定义了两种操作：
1. add 将区间[L，R]内的数全部加上x；
2. query 询问在区间[L，R]内，最大的上升子序列（CIS）的长度。
这里LCIS是一段连续的序列，不同于LIS，后者可以跳过一些数。
解题思路：
对区间的操作，自然想到线段树。
我们在线段树seg[4*N+100]的节点中保存7个域：L、R、Llen、Rlen、MaxLen、add、len。我们稍后看看如何对这7个域操作。先对这7个域描述一下：
L：该区间左端点值；
R：该区间右端点值；
Llen：从左端点开始的LCIS的长度；
Rlen：到右端点结束的LCIS的长度；
MaxLen：包含在该区间内的LCIS的长度。
add：该区间全部元素都要加上add；
len：仅仅在query函数的返回参数中有用。
首先是对线段树的初始化了。我们将每个位置视为区间[L，L+0]。从线段树根节点开始找下去，直到找到该区间，这时我们到达一个叶子节点，对该叶子节点初始化，再顺着路径返回到根节点。返回过程中在合适时候初始化中间节点。
对叶子节点的初始化：（x为该点的值）
L = R = x；
Llen = Rlen = MaxLen = 1；
add = 0；
对中间节点仅在其所有子节点都初始化后再进行初始化（这样所有中间节点都会初始化，且仅一次）：
此时根据其两个子节点seg[i*2]和seg[i*2+1]进行初始化，以满足我们对节点各个域的描述（上面我们是如何描述这7个域的？）。
下面描述update和query。
我们先定义几个名词：
包含节点：若要更新或查询的目标区间为[l，r]，满足l<=L && R<=r的区间 称为包含节点，此时该节点表示的区间完全包含在目标区间内。
完全不包含节点：该节点表示的区间和目标区间没有交集。
左子区间包含：该节点右子节点是完全不包含节点，左子节点不是。
右子区间包含：该节点左子节点是完全不包含节点，右子节点不是。
对区间的更新我们用update函数实现。
我们注意到：
1. 将一段区间每个数加上一个数x后，其内部的相对大小不改变，该区间对包含它的更大的区间的影响仅仅通过区间端点值L，R实现。即在初始化和每次更新后，每个区间都能屏蔽其子区间对上面的影响。
2. 对该区间的子区间查询结果，仅在返回到该节点之上更大的区间时，在该区间整体加上的值x会对返回结果产生影响。此时在返回至该区间时，对结果的端点值修饰（加上该区间的add值）即可。从上面的区间看下来，就像我们对每个子区间都更新了。
从根节点开始，若遇到包含节点完成更新后就返回，遇到完全不包含区间直接返回。否则递归更新其左子节点、右子节点，直至到了一个包含节点或完全不包含节点。
返回时，沿途更新所有节点。
对包含节点的更新：L+=x、 R+=x、 add+=x。
对中间节点更新（返回时）：更新其Llen、Rlen、MaxLen，方法和初始化时是一样的。add、len不更新。跟新L和R不是子区间端点值，而是子区间的端点值加上该节点的add值，因为我们的子区间值可能被屏蔽了，不是最新的值。
query函数完成查询。
1.查询到包含节点：返回包含节点的值，并在len域注明区间长度。
2.查询到左子区间包含或右子区间包含的节点，仅对其左子节点或右子节点递归查询。对返回的结果修饰（结果的端点值L和R加上该区间记录的add值）后，返回。
3.其他情况既需对左子区间又需对右子区间查询，得到两个返回结果：ndj和ndk，将两个结果合并为一个结果，再对结果修饰（结果的端点值L和R加上该区间记录的add值）后，返回。
源代码：
#include<cstdio>
#include<iostream>
char chrn;
#define SCRN while(scanf("%c",&ch) && ch!='\n');
using namespace std;
typedef struct
{
int Llen,Rlen,MaxLen,add,len,R,L;
}node;
node seg[400100];
int max(int a,int b,int c,int d,int e)
{
int x=a;
if(b>x)
x=b;
if(c>x)
x=c;
if(d>x)
x=d;
if(e>x)
x=e;
return x;
}
void ini(int i,int L,int R,int loc,int x)
{
int mid=(L+R)/2, j=2*i, k=j+1;
int m;
if(L==R)//leaf node
{
seg[i].Llen=1;
seg[i].Rlen=1;
seg[i].MaxLen=1;
seg[i].L=x;
seg[i].R=x;
seg[i].add=0;
return;
}
if(loc<=mid)
ini(j,L,mid,loc,x);
else
ini(k,mid+1,R,loc,x);
if(loc==R)//mid node
{
seg[i].L=seg[j].L;
seg[i].R=seg[k].R;
seg[i].add=0;
if(seg[j].R < seg[k].L)
{
if(seg[j].Llen == mid-L+1)
seg[i].Llen=seg[j].Llen+seg[k].Llen;
else
seg[i].Llen=seg[j].Llen;
if(seg[k].Rlen == R-mid)
seg[i].Rlen=seg[j].Rlen+seg[k].Rlen;
else
seg[i].Rlen=seg[k].Rlen;
m=seg[j].Rlen+seg[k].Llen;
}
else
{
seg[i].Llen=seg[j].Llen;
seg[i].Rlen=seg[k].Rlen;
m=0;
}
seg[i].MaxLen = max(seg[i].Llen, seg[i].Rlen, seg[j].MaxLen, seg[k].MaxLen, m);
}
}
void update(int i,int L,int R,int l,int r,int x)
{
int mid=(L+R)/2,j=2*i,k=j+1;
int m;
if(l<=L && R<=r)//included
{
seg[i].L+=x;
seg[i].R+=x;
seg[i].add+=x;
return ;
}
else if(l>R || L>r)
return ;
update(j,L,mid,l,r,x);
update(k,mid+1,R,l,r,x);
//update
seg[i].L=seg[j].L+seg[i].add;//关键要加上eg[i].add!!!!!!!!!!!!!!!!!!!!!!!!!!
seg[i].R=seg[k].R+seg[i].add;
if(seg[j].R < seg[k].L)
{
if(seg[j].Llen == mid-L+1)
seg[i].Llen=seg[j].Llen+seg[k].Llen;
else
seg[i].Llen=seg[j].Llen;
if(seg[k].Rlen == R-mid)
seg[i].Rlen=seg[j].Rlen+seg[k].Rlen;
else
seg[i].Rlen=seg[k].Rlen;
m=seg[j].Rlen+seg[k].Llen;
}
else
{
seg[i].Llen=seg[j].Llen;
seg[i].Rlen=seg[k].Rlen;
m=0;
}
seg[i].MaxLen = max(seg[i].Llen, seg[i].Rlen, seg[j].MaxLen, seg[k].MaxLen, m);
}
node query(int i,int L,int R,int l,int r)
{
int mid=(L+R)/2, j=i*2, k=j+1, m, add=seg[i].add;
node ndj,ndk,nd;
if(l<=L && R<=r)
{
nd=seg[i];
nd.len=R-L+1;
return nd;
}
else if(l>mid)
{
nd=query(k,mid+1,R,l,r);
nd.L+=add;
nd.R+=add;
return nd;
}
else if(r<=mid)
{
nd=query(j,L,mid,l,r);
nd.L+=add;
nd.R+=add;
return nd;
}
else
{
ndj=query(j,L,mid,l,r);
ndk=query(k,mid+1,R,l,r);
nd.L=ndj.L;
nd.R=ndk.R;
nd.len=ndj.len+ndk.len;
if(ndj.R<ndk.L)
{
if(ndj.Llen == ndj.len)
nd.Llen=ndj.Llen+ndk.Llen;
else
nd.Llen=ndj.Llen;
if(ndk.Rlen == ndk.len)
nd.Rlen=ndj.Rlen+ndk.Rlen;
else
nd.Rlen=ndk.Rlen;
m=ndj.Rlen+ndk.Llen;
}
else
{
nd.Llen=ndj.Llen;
nd.Rlen=ndk.Rlen;
m=0;
}
nd.MaxLen = max(nd.Llen, nd.Rlen, ndj.MaxLen, ndk.MaxLen, m);
nd.L+=add;
nd.R+=add;
return nd;
}
}
int main()
{
int t,T,i,N,Q,r,l;
int x;
node nd;
char ch;
//freopen("1425in.txt","r",stdin);
cin>>T;
for(t=1; t<=T; t++)
{
cin>>N>>Q;
for(i=0; i<=4*N; i++)
{
seg[i].add=0;
seg[i].len=0;
seg[i].Llen=seg[i].Rlen=seg[i].MaxLen=0;
}
for(i=1; i<=N; i++)
{
scanf("%d",&x);
ini(1,1,N,i,x);
}
printf("Case #%d:\n",t);
for(i=1; i<=Q; i++)
{
SCRN
scanf("%c",&ch);
if(ch=='a')
{
scanf("%d %d %d",&l,&r,&x);
update(1,1,N,l,r,x);
}
else if(ch=='q')
{
scanf("%d %d",&l,&r);
nd=query(1,1,N,l,r);
printf("%d\n",nd.MaxLen);
}
}
}
return 0;
}