首页 > 代码库 > (中等) UESTC 360 Another LCIS ，线段树+区间更新。
(中等) UESTC 360 Another LCIS ，线段树+区间更新。
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[100005*4];int COL[100005*4];int num[100005];void pushDown(int po){ if(COL[po]) { COL[po*2]+=COL[po]; COL[po*2+1]+=COL[po]; BIT[po*2].x+=COL[po]; BIT[po*2].y+=COL[po]; BIT[po*2+1].x+=COL[po]; BIT[po*2+1].y+=COL[po]; COL[po]=0; }}void pushUP(int L,int R,int po){ BIT[po].mid=max(BIT[po*2].mid,BIT[po*2+1].mid); BIT[po].lef=BIT[po*2].lef; BIT[po].rig=BIT[po*2+1].rig; BIT[po].x=BIT[po*2].x; BIT[po].y=BIT[po*2+1].y; int M=(L+R)/2; if(BIT[po*2].y<BIT[po*2+1].x) { BIT[po].mid=max(BIT[po].mid,BIT[po*2].rig+BIT[po*2+1].lef); if(BIT[po*2].lef==M-L+1) BIT[po].lef=M-L+1+BIT[po*2+1].lef; if(BIT[po*2+1].rig==R-M) BIT[po].rig=R-M+BIT[po*2].rig; }}void build_tree(int L,int R,int po){ if(L==R) { BIT[po].lef=BIT[po].rig=BIT[po].mid=1; scanf("%d",&COL[po]); BIT[po].x=BIT[po].y=COL[po]; return; } int M=(L+R)/2; COL[po]=0; 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)/2; 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)/2; 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*2].y<BIT[po*2+1].x) maxn=max(maxn,min(M-ql+1,BIT[po*2].rig)+min(qr-M,BIT[po*2+1].lef)); return maxn; }}int main(){ int T; char ch[5]; int a,b,c; cin>>T; for(int cas=1;cas<=T;++cas) { printf("Case #%d:\n",cas); scanf("%d %d",&N,&Q); build_tree(1,N,1); for(int i=1;i<=Q;++i) { scanf("%s",ch); if(ch[0]==‘q‘) { scanf("%d %d",&a,&b); printf("%d\n",query(a,b,1,N,1)); } else { scanf("%d %d %d",&a,&b,&c); update(a,b,c,1,N,1); } } } return 0;}
(中等) UESTC 360 Another LCIS ，线段树+区间更新。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。