Description:
For a sequence S1,S2,⋯,SN, and a pair of integers (i,j), if 1≤i≤j≤N and Si<Si+1<Si+2<⋯<Sj−1<Sj, then the sequence Si,Si+1,⋯,Sj is a CIS
(Continuous Increasing Subsequence). The longest CIS
of a sequence is called the LCIS
(Longest Continuous Increasing Subsequence).
In this problem, we will give you a sequence first, and then some add
operations and some query
operations. An add operation adds a value to each member in a specified interval. For a query operation, you should output the length of the LCIS of a specified interval.
题目大意就是说求一段区间的最大上升子序列(注意这里的子序列必须是连续的。)
对线段树维护前缀最大上升子序列,后缀最大上升子序列,最大上升子序列,以及区间左端点的值,右端点的值。
这里要注意如果pushUP时,左子树前缀为其长度,那么父亲的前缀的长度应该为左的加右的,右子树同理。
代码如下:
#include<iostream>
#include<cstdio>#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define lson L,M,po*2
#define rson M+1,R,po*2+1using namespace std;struct state
{
int lef,rig,mid;
int x,y;
};int N,Q;
state BIT[*];
int COL[*];
int num[];void pushDown(int po)
{
if(COL[po])
{
COL[po*]+=COL[po];
COL[po*+]+=COL[po];
BIT[po*].x+=COL[po];
BIT[po*].y+=COL[po];
BIT[po*+].x+=COL[po];
BIT[po*+].y+=COL[po];
COL[po]=;
}
}void pushUP(int L,int R,int po)
{
BIT[po].mid=max(BIT[po*].mid,BIT[po*+].mid);
BIT[po].lef=BIT[po*].lef;
BIT[po].rig=BIT[po*+].rig;
BIT[po].x=BIT[po*].x;
BIT[po].y=BIT[po*+].y; int M=(L+R)/; if(BIT[po*].y<BIT[po*+].x)
{
BIT[po].mid=max(BIT[po].mid,BIT[po*].rig+BIT[po*+].lef); if(BIT[po*].lef==M-L+)
BIT[po].lef=M-L++BIT[po*+].lef;
if(BIT[po*+].rig==R-M)
BIT[po].rig=R-M+BIT[po*].rig;
}
}void build_tree(int L,int R,int po)
{
if(L==R)
{
BIT[po].lef=BIT[po].rig=BIT[po].mid=;
scanf("%d",&COL[po]);
BIT[po].x=BIT[po].y=COL[po];
return;
} int M=(L+R)/; COL[po]=; build_tree(lson);
build_tree(rson); pushUP(L,R,po);
}void update(int ul,int ur,int add,int L,int R,int po)
{
if(ul<=L&&ur>=R)
{
COL[po]+=add;
BIT[po].x+=add;
BIT[po].y+=add;
return;
} pushDown(po); int M=(L+R)/; if(ul<=M)
update(ul,ur,add,lson);
if(ur>M)
update(ul,ur,add,rson); pushUP(L,R,po);
}int query(int ql,int qr,int L,int R,int po)
{
if(ql<=L&&qr>=R)
return BIT[po].mid; pushDown(po); int M=(L+R)/;
int maxn; if(ql>M)
return query(ql,qr,rson);
else if(qr<=M)
return query(ql,qr,lson);
else
{
maxn=max(query(ql,qr,lson),query(ql,qr,rson)); if(BIT[po*].y<BIT[po*+].x)
maxn=max(maxn,min(M-ql+,BIT[po*].rig)+min(qr-M,BIT[po*+].lef)); return maxn;
}
}int main()
{
int T;
char ch[];
int a,b,c;
cin>>T; for(int cas=;cas<=T;++cas)
{
printf("Case #%d:\n",cas); scanf("%d %d",&N,&Q); build_tree(,N,); for(int i=;i<=Q;++i)
{
scanf("%s",ch); if(ch[]=='q')
{
scanf("%d %d",&a,&b);
printf("%d\n",query(a,b,,N,));
}
else
{
scanf("%d %d %d",&a,&b,&c);
update(a,b,c,,N,);
}
}
} return ;
}