首页 > 代码库 > (简单) HDU 3308 LCIS，线段树+区间合并。
(简单) HDU 3308 LCIS，线段树+区间合并。
Problem Description
Given n integers.
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].
题目大意就是给你一个数列，求区间内的最长连续子序列。以及对某一个点的值进行更改。
线段树维护区间内的LCIS，前缀LCIS，后缀LCIS就可。
代码如下：
#include<iostream>#include<cstdio>#include<cstring>#define lson L,M,po*2#define rson M+1,R,po*2+1#define lc po*2#define rc po*2+1using namespace std;const int maxn=10e5+10;int mBIT[maxn*4],lBIT[maxn*4],rBIT[maxn*4];int num[maxn];void pushUP(int po,int len,int M){ mBIT[po]=max(mBIT[lc],mBIT[rc]); lBIT[po]=lBIT[lc]; rBIT[po]=rBIT[rc]; if(num[M]<num[M+1]) { mBIT[po]=max(mBIT[po],rBIT[lc]+lBIT[rc]); if(lBIT[lc]==len-(len/2)) lBIT[po]+=lBIT[rc]; if(rBIT[rc]==(len/2)) rBIT[po]+=rBIT[lc]; }}void build_tree(int L,int R,int po){ if(L==R) { scanf("%d",&num[L]); mBIT[po]=lBIT[po]=rBIT[po]=1; return; } int M=(L+R)/2; build_tree(lson); build_tree(rson); pushUP(po,R-L+1,M);}void update(int up,int L,int R,int po){ if(L==R&&L==up) return; int M=(L+R)/2; if(up<=M) update(up,lson); else update(up,rson); pushUP(po,R-L+1,M);}int query(int ql,int qr,int L,int R,int po){ if(ql<=L&&qr>=R) return mBIT[po]; int M=(L+R)/2; if(qr<=M) return query(ql,qr,lson); if(ql>M) return query(ql,qr,rson); int ans=max(query(max(ql,L),M,lson),query(M+1,min(qr,R),rson)); int temp=min(rBIT[lc],M-ql+1)+min(lBIT[rc],qr-M); if(num[M]<num[M+1]) //这里要判断！ return max(ans,temp); else return ans;}int main(){ int N,M; int a,b; char c[5]; int T; cin>>T; while(T--) { scanf("%d %d",&N,&M); build_tree(0,N-1,1); while(M--) { scanf("%s %d %d",c,&a,&b); if(c[0]==‘Q‘) printf("%d\n",query(a,b,0,N-1,1)); else { num[a]=b; update(a,0,N-1,1); } } } return 0;}
(简单) HDU 3308 LCIS，线段树+区间合并。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。