关键词：
LCIS
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6592 Accepted Submission(s): 2866
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
Each case starts with two integers n , m(0<n,m<=105).
The next line has n integers(0<=val<=105).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=105)
OR
Q A B(0<=A<=B< n).
#include<bits/stdc++.h> using namespace std; #define ll long long #define pi (4*atan(1.0)) const int N=1e5+10,M=4e6+10,inf=1e9+10; struct is { int l,r; int lm,mm,rm; }tree[N<<2]; int val[N]; void buildtree(int l,int r,int pos) { tree[pos].l=l; tree[pos].r=r; if(l==r) { tree[pos].lm=tree[pos].rm=tree[pos].mm=1; return; } int mid=(l+r)>>1; buildtree(l,mid,pos<<1); buildtree(mid+1,r,pos<<1|1); tree[pos].lm=tree[pos<<1].lm; tree[pos].rm=tree[pos<<1|1].rm; if(val[tree[pos<<1].r]<val[tree[pos<<1|1].l]) tree[pos].mm=max(tree[pos<<1].mm,max(tree[pos<<1|1].mm,tree[pos<<1].rm+tree[pos<<1|1].lm)); else tree[pos].mm=max(tree[pos<<1].mm,tree[pos<<1|1].mm); if(val[tree[pos<<1].r]<val[tree[pos<<1|1].l]&&tree[pos<<1].lm==tree[pos<<1].r-tree[pos<<1].l+1) tree[pos].lm+=tree[pos<<1|1].lm; if(val[tree[pos<<1].r]<val[tree[pos<<1|1].l]&&tree[pos<<1|1].rm==tree[pos<<1|1].r-tree[pos<<1|1].l+1) tree[pos].rm+=tree[pos<<1].rm; } void update(int point,int pos) { if(tree[pos].l==tree[pos].r) return; int mid=(tree[pos].r+tree[pos].l)>>1; if(point>mid) update(point,pos<<1|1); else update(point,pos<<1); tree[pos].lm=tree[pos<<1].lm; tree[pos].rm=tree[pos<<1|1].rm; if(val[tree[pos<<1].r]<val[tree[pos<<1|1].l]) tree[pos].mm=max(tree[pos<<1].mm,max(tree[pos<<1|1].mm,tree[pos<<1].rm+tree[pos<<1|1].lm)); else tree[pos].mm=max(tree[pos<<1].mm,tree[pos<<1|1].mm); if(val[tree[pos<<1].r]<val[tree[pos<<1|1].l]&&tree[pos<<1].lm==tree[pos<<1].r-tree[pos<<1].l+1) tree[pos].lm+=tree[pos<<1|1].lm; if(val[tree[pos<<1].r]<val[tree[pos<<1|1].l]&&tree[pos<<1|1].rm==tree[pos<<1|1].r-tree[pos<<1|1].l+1) tree[pos].rm+=tree[pos<<1].rm; } is query(int L,int R,int pos) { if(tree[pos].l==L&&tree[pos].r==R) return tree[pos]; int mid=(tree[pos].l+tree[pos].r)>>1; if(mid<L) return query(L,R,pos<<1|1); else if(mid>=R) return query(L,R,pos<<1); else { is a=query(L,mid,pos<<1); is b=query(mid+1,R,pos<<1|1); is ans; ans.l=a.l,ans.r=b.r; ans.lm=a.lm; ans.rm=b.rm; if(val[a.r]<val[b.l]) ans.mm=max(a.mm,max(b.mm,a.rm+b.lm)); else ans.mm=max(a.mm,b.mm); if(val[a.r]<val[b.l]&&a.lm==a.r-a.l+1) ans.lm+=b.lm; if(val[a.r]<val[b.l]&&b.rm==b.r-b.l+1) ans.rm+=a.rm; return ans; } } char a[10]; int main() { int T; scanf("%d",&T); while(T--) { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&val[i]); buildtree(1,n,1); while(m--) { int l,r; scanf("%s%d%d",a,&l,&r); l++; if(a[0]==‘U‘) val[l]=r,update(l,1); else r++,printf("%d ",query(l,r,1).mm); } } return 0; }
hdu3308lcis(经典区间合并)线段树
...二是查询某个区间的LCIS(最长上升子序列）。解题分析：线段树区间合并的典型例题，用求某个区间的LCIS时，需要比较三个值，一是左区间的LCIS，二是右区间的LCIS,三是左右子区间合并的LCIS。最重要的是第三点如何实现，实现... 查看详情
hdu3308lcis线段树区间更新
...间x-y的最长连续上升子序列的长度L 解题思路：对于线段树不好的我依然好难.....有太多细节需要注意了....但是这是一道很好的题，一段区间的L可能从三个地方来，一种是中间，一种是以左起点为开头的，一 查看详情
hdu--3308lcis（线段树+区间合并）
DescriptionGivennintegers. Youhavetwooperations: UAB:replacetheAthnumberbyB.(indexcountingfrom0) QAB:outputthelengthofthelongestconsecutiveincreasingsubsequence(LCIS)in[a,b]. Input 查看详情
hdu3308lcis（线段树区间合并）
...度。对于每次询问，输出一个答案 题解：一道简单的线段树区间合并，一般线段树的区间合并都会设lsum,rsum，表示左连续和右连续还有sum表示总共的 查看详情
hdu1540tunnelwarfare（线段树，单点更新，区间查询）
ProblemDescriptionDuringtheWarofResistanceAgainstJapan,tunnelwarfarewascarriedoutextensivelyinthevastareasofnorthChinaPlain.Generallyspeaking,villagesconnectedbytunnelslayinaline.Exceptthetwoattheends 查看详情
hdu1754ihateit（线段树单点更新区间查询最值）
HDU1754IHateIthttp://acm.hdu.edu.cn/showproblem.php?pid=1754//////////////////注意线段树的大小要比需要使用线段树的数据的个数大个3到4倍//////////////////////////////////////////IHateItTimeLimit:9000/3000MS(Java/Others) &nbs 查看详情
[hdoj3308]lcis（线段树，区间合并）
...上升子序列的长度。注意到‘连续’一词，可以用线段树维护[L,R]区间内的LICS。定义结构Node，内部ls，rs为左右儿子的下标。l，r记录当前区间分别从左起和右起的LICS长度，s记 查看详情
hdoj题目3308lcis（线段树，区间查询，区间合并）
LCISTimeLimit:6000/2000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):5319 AcceptedSubmission(s):2361ProblemDescriptionGivenninte 查看详情
hdu1754ihateit（线段树之单点更新区间最值查询）(代码片段)
IHateItTimeLimit:9000/3000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):101699 AcceptedSubmission(s):38294ProblemDescription很多学校 查看详情
[hdoj3308]lcis（线段树，区间合并，新的代码）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3308题意：给定n个数，两个操作：UAB：将位置A的数值改成BQAB：查询[A,B]内最长连续上升子序列的长度。 我认为当时的代码风格和现在的不一样（因为喜欢在Seg里存l和r的下标，然而... 查看详情
hdu1166-敌兵布阵-[单点修改区间查询zkw线段树]
...：http://www.cnblogs.com/dilthey/p/6827959.html不过我们今天换一种线段树实现来做这道题；关于zkw线段树的讲解：https://zhuanlan.zhihu.com/p/29876526（而且我还在文章里被@了，超开心的ヾ(≧?≦*)ヾ）可以说是讲解非常的清楚了！ AC代码（... 查看详情
hdu3397sequenceoperation线段树区间更新区间合并
题意：5种操作，所有数字都为0或10ab：将[a,b]置01ab：将[a,b]置12ab：[a,b]中的0和1互换3ab：查询[a,b]中的1的数量4ab：查询[a,b]中的最长连续1串的长度这题看题目就很裸，综合了区间更新，区间合并我一开始把更新操作全放一个变量... 查看详情
hdu1166敌兵布阵（线段树单点更新）
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，... 查看详情
hdu2871线段树区间更新
不得已又挖了一个坑。。想来学习线段树也有一段时间了，也有了些了解，但是在做题的时候还是磕磕碰碰的，还是不够熟练，还是要多做题（水题除外），多思考。这是一道典型的线段树区间更新，一定要使用延迟标记，同时... 查看详情
hdu1166线段树（单点更新，区间求和）
敌兵布阵TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):78691 AcceptedSubmission(s):33255ProblemDescriptionC国的死对头A国 查看详情
hdu1116敌兵布阵线段树区间求和单点更新
线段树的基本知识可以先google一下，不是很难理解线段树功能:update:单点增减query:区间求和#include<bits/stdc++.h>#definelsonl,m,rt<<1#definersonm+1,r,rt<<1|1usingnamespacestd;constintMAXN=50008;intsum[MAXN<<2];voi 查看详情
hdu5861road（线段树区间修改单点查询）
RoadTimeLimit:12000/6000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):1132 AcceptedSubmission(s):309ProblemDescriptionTherearenv 查看详情
hdu1698justahook线段树区间更新
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1698 题目描述：区间更新，最后求出1~n之和 解题思路：这里涉及到区间更新，这也是我第一次写区间更新，以前都是单点更新，回溯就可以了，如果将区间更... 查看详情