首页 > 代码库 > 线段树题目汇总
线段树题目汇总
区间合并部分：
POJ 3667 Hotel
求某大于等于a的最长区间
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #define LEN 50001<<2 using namespace std; struct Line_tree { //分别表示以当前区间为左端点的最长连续空白区间，为右端点的最长连续空白区间，该区间的最长连续空白区间，该区间的懒惰标记 int lt[LEN],rt[LEN],maxt[LEN],tar[LEN]; void build(int o,int L,int R) { lt[o]=rt[o]=maxt[o]=R-L+1; tar[o]=-1; if(L==R) return ; int M=L+(R-L)/2; build(o<<1,L,M); build(o<<1|1,M+1,R); } void push_down(int o,int m) { if(tar[o]!=-1) { tar[o<<1]=tar[o<<1|1]=tar[o]; if(tar[o]==1) lt[o<<1]=rt[o<<1]=maxt[o<<1]=lt[o<<1|1]=rt[o<<1|1]=maxt[o<<1|1]=0; else { lt[o<<1]=rt[o<<1]=maxt[o<<1]=m-(m>>1); lt[o<<1|1]=rt[o<<1|1]=maxt[o<<1|1]=m>>1; } tar[o]=-1; } } void push_up(int o,int m) { if(lt[o<<1]==m-(m>>1)) lt[o]=lt[o<<1]+lt[o<<1|1]; else lt[o]=lt[o<<1]; if(rt[o<<1|1]==m>>1) rt[o]=rt[o<<1|1]+rt[o<<1]; else rt[o]=rt[o<<1|1]; maxt[o]=max(rt[o<<1]+lt[o<<1|1],max(maxt[o<<1],maxt[o<<1|1])); } int query(int len,int L,int R,int o) { if(L==R) return L; push_down(o,R-L+1); int M=L+(R-L)/2; if(maxt[o<<1]>=len) return query(len,L,M,o<<1); else if(rt[o<<1]+lt[o<<1|1]>=len) return M-rt[o<<1]+1; else return query(len,M+1,R,o<<1|1); } void update(int ql,int qr,int c,int L,int R,int o) { if(ql<=L&&R<=qr) { if(c==1) lt[o]=rt[o]=maxt[o]=0; else lt[o]=rt[o]=maxt[o]=R-L+1; tar[o]=c; } else { push_down(o,R-L+1); int M=L+(R-L)/2; if(ql<=M) update(ql,qr,c,L,M,o<<1); if(M<qr) update(ql,qr,c,M+1,R,o<<1|1); push_up(o,R-L+1); } } }; Line_tree tree; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { tree.build(1,1,n); while(m--) { int p,a,b; scanf("%d",&p); if(p==1) { scanf("%d",&a); if(a>tree.maxt[1]) puts("0"); else { int pos=tree.query(a,1,n,1); printf("%d\n",pos); tree.update(pos,pos+a-1,1,1,n,1); } } else { scanf("%d%d",&a,&b); tree.update(a,a+b-1,0,1,n,1); } } } return 0; }
HDU 3308 LCIS
求某区间最长子串长度。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #define LEN 100001<<2 using namespace std; int arr[100005]; struct Line_tree { int lt[LEN],rt[LEN],maxt[LEN]; void push_up(int o,int L,int R) { int m=R-L+1,M=L+(R-L)/2; if(lt[o<<1]==m-(m>>1)&&arr[M]<arr[M+1]) lt[o]=lt[o<<1]+lt[o<<1|1]; else lt[o]=lt[o<<1]; if(rt[o<<1|1]==(m>>1)&&arr[M]<arr[M+1]) rt[o]=rt[o<<1]+rt[o<<1|1]; else rt[o]=rt[o<<1|1]; maxt[o]=max(maxt[o<<1],maxt[o<<1|1]); if(arr[M]<arr[M+1]) maxt[o]=max(maxt[o],rt[o<<1]+lt[o<<1|1]); } void build(int o,int L,int R) { if(L==R) lt[o]=rt[o]=maxt[o]=1; else { int M=L+(R-L)/2; build(o<<1,L,M); build(o<<1|1,M+1,R); push_up(o,L,R); } } void update(int o,int pos,int val,int L,int R) { if(L==R) arr[L]=val; else { int M=L+(R-L)/2; if(pos<=M) update(o<<1,pos,val,L,M); else update(o<<1|1,pos,val,M+1,R); push_up(o,L,R); } } int query(int o,int ql,int qr,int L,int R) { if(ql<=L&&R<=qr) return maxt[o]; else { int M=L+(R-L)/2; int maxn=0; if(ql<=M) maxn=max(maxn,query(o<<1,ql,qr,L,M)); if(M<qr) maxn=max(maxn,query(o<<1|1,ql,qr,M+1,R)); if(ql<=M&&M<qr&&arr[M]<arr[M+1]) maxn=max(maxn,min(M+lt[o<<1|1],qr)-max(M-rt[o<<1]+1,ql)+1); return maxn; } } }; Line_tree tree; 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",&arr[i]); tree.build(1,1,n); while(m--) { char p[3]; int a,b; scanf("%s%d%d",p,&a,&b); if(p[0]==‘Q‘) { a++; b++; printf("%d\n",tree.query(1,a,b,1,n)); } else { a++; tree.update(1,a,b,1,n); } } } return 0; }
HDU 3397 Sequence operation
要用两个懒惰标记来做。
同时维护区间1的个数（这个比较好做），另外还要维护区间连续的最长1和0的长度（各开三个数组，分别是以区间左端点为左端点、以区间右端点为右端点和区间最大长度三种情况）。置1和置0的情况使用同一个懒惰标记，这个比较好做。难点在于异或的时候，如果在某个结点执行异或操作，如果该结点存在非空的置1/0的懒惰标记，这时候就把该非空的
1/0的懒惰标记颠倒，即置1变成置0，置0变成置1，否则的话就标记一个异或标记。这个时候要把最长的1和0的长度交换。
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #define LEN 100001<<2 using namespace std; int arr[100001]; struct Line_tree { int lz[LEN],rz[LEN],maxz[LEN]; int lo[LEN],ro[LEN],maxo[LEN]; int tar[LEN],txr[LEN],sum[LEN]; void fill_val(int o,int c,int L,int R) { tar[o]=c; txr[o]=0; if(c==0) { lz[o]=rz[o]=maxz[o]=R-L+1; lo[o]=ro[o]=maxo[o]=0; sum[o]=0; } else { lz[o]=rz[o]=maxz[o]=0; lo[o]=ro[o]=maxo[o]=R-L+1; sum[o]=R-L+1; } } void fill_xor(int o,int L,int R) { if(tar[o]!=-1) tar[o]^=1; else txr[o]^=1; sum[o]=R-L+1-sum[o]; swap(lo[o],lz[o]); swap(ro[o],rz[o]); swap(maxo[o],maxz[o]); } void push_down(int o,int L,int R) { int m=R-L+1,M=L+(R-L)/2; if(tar[o]!=-1) { fill_val(o<<1,tar[o],L,M); fill_val(o<<1|1,tar[o],M+1,R); tar[o]=-1; } if(txr[o]) { fill_xor(o<<1,L,M); fill_xor(o<<1|1,M+1,R); txr[o]=0; } } void push_up(int o,int L,int R) { sum[o]=sum[o<<1]+sum[o<<1|1]; int M=L+(R-L)/2,m=R-L+1; if(lo[o<<1]==m-(m>>1)) lo[o]=lo[o<<1]+lo[o<<1|1]; else lo[o]=lo[o<<1]; if(ro[o<<1|1]==(m>>1)) ro[o]=ro[o<<1]+ro[o<<1|1]; else ro[o]=ro[o<<1|1]; maxo[o]=max(maxo[o<<1],maxo[o<<1|1]); maxo[o]=max(maxo[o],ro[o<<1]+lo[o<<1|1]); if(lz[o<<1]==m-(m>>1)) lz[o]=lz[o<<1]+lz[o<<1|1]; else lz[o]=lz[o<<1]; if(rz[o<<1|1]==(m>>1)) rz[o]=rz[o<<1]+rz[o<<1|1]; else rz[o]=rz[o<<1|1]; maxz[o]=max(maxz[o<<1],maxz[o<<1|1]); maxz[o]=max(maxz[o],rz[o<<1]+lz[o<<1|1]); } void build(int o,int L,int R) { tar[o]=-1; txr[o]=0; if(L==R) { if(arr[L]==1) { sum[o]=lo[o]=ro[o]=maxo[o]=1; lz[o]=rz[o]=maxz[o]=0; } else { sum[o]=lo[o]=ro[o]=maxo[o]=0; lz[o]=rz[o]=maxz[o]=1; } } else { int M=L+(R-L)/2; build(o<<1,L,M); build(o<<1|1,M+1,R); push_up(o,L,R); } } void update(int o,int c,int ql,int qr,int L,int R) { if(ql<=L&&R<=qr) { if(c<2) fill_val(o,c,L,R); else if(c==2) fill_xor(o,L,R); } else { push_down(o,L,R); int M=L+(R-L)/2; if(ql<=M) update(o<<1,c,ql,qr,L,M); if(M<qr) update(o<<1|1,c,ql,qr,M+1,R); push_up(o,L,R); } } int query(int o,int c,int ql,int qr,int L,int R) { if(ql<=L&&R<=qr) return c==4?maxo[o]:sum[o]; else { push_down(o,L,R); int M=L+(R-L)/2,m=R-L+1,maxn=0,s=0; if(c==4) { if(ql<=M) maxn=max(maxn,query(o<<1,c,ql,qr,L,M)); if(M<qr) maxn=max(maxn,query(o<<1|1,c,ql,qr,M+1,R)); if(ql<=M&&M<qr) maxn=max(maxn,min(qr,M+lo[o<<1|1])-max(ql,M-ro[o<<1]+1)+1); return maxn; } else { if(ql<=M) s+=query(o<<1,c,ql,qr,L,M); if(M<qr) s+=query(o<<1|1,c,ql,qr,M+1,R); return s; } } } }; Line_tree tree; 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",&arr[i]); tree.build(1,1,n); while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); b++; c++; if(a<=2) tree.update(1,a,b,c,1,n); else printf("%d\n",tree.query(1,a,b,c,1,n)); } } return 0; }
UPC 2555 Longest Non-decreasing Substring
同时维护区间非递增和非递减的最长区间长度。另外要再开两个数组分别维护当前区间的左端点取值和右端点取值，它们的值分别在push_up的时候来自子节点的值。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #define LEN 100001<<2 using namespace std; char str[100005]; int n,m; struct Line_Tree { int lu[LEN],ru[LEN],maxu[LEN]; int ld[LEN],rd[LEN],maxd[LEN]; int left[LEN],right[LEN]; int tar[LEN]; int filp(int x) { return 9-x; } void fill_xor(int o,int L,int R) { int M=L+(R-L)/2; tar[o]^=1; left[o]=filp(left[o]); right[o]=filp(right[o]); swap(lu[o],ld[o]); swap(ru[o],rd[o]); swap(maxu[o],maxd[o]); } void push_up(int o,int L,int R) { int M=L+(R-L)/2,m=R-L+1; left[o]=left[o<<1]; right[o]=right[o<<1|1]; if(lu[o<<1]==m-(m>>1)&&right[o<<1]<=left[o<<1|1]) lu[o]=lu[o<<1]+lu[o<<1|1]; else lu[o]=lu[o<<1]; if(ru[o<<1|1]==(m>>1)&&right[o<<1]<=left[o<<1|1]) ru[o]=ru[o<<1]+ru[o<<1|1]; else ru[o]=ru[o<<1|1]; maxu[o]=max(maxu[o<<1],maxu[o<<1|1]); if(right[o<<1]<=left[o<<1|1]) maxu[o]=max(maxu[o],ru[o<<1]+lu[o<<1|1]); if(ld[o<<1]==m-(m>>1)&&right[o<<1]>=left[o<<1|1]) ld[o]=ld[o<<1]+ld[o<<1|1]; else ld[o]=ld[o<<1]; if(rd[o<<1|1]==(m>>1)&&right[o<<1]>=left[o<<1|1]) rd[o]=rd[o<<1]+rd[o<<1|1]; else rd[o]=rd[o<<1|1]; maxd[o]=max(maxd[o<<1],maxd[o<<1|1]); if(right[o<<1]>=left[o<<1|1]) maxd[o]=max(maxd[o],rd[o<<1]+ld[o<<1|1]); } void push_down(int o,int L,int R) { int M=L+(R-L)/2; if(tar[o]) { fill_xor(o<<1,L,M); fill_xor(o<<1|1,M+1,R); tar[o]=0; } } void build(int o,int L,int R) { tar[o]=0; left[o]=str[L]-‘0‘; right[o]=str[R]-‘0‘; if(L==R) { lu[o]=ru[o]=maxu[o]=1; ld[o]=rd[o]=maxd[o]=1; } else { int M=L+(R-L)/2; build(o<<1,L,M); build(o<<1|1,M+1,R); push_up(o,L,R); } } void update(int o,int ql,int qr,int L,int R) { if(ql<=L&&R<=qr) fill_xor(o,L,R); else { push_down(o,L,R); int M=L+(R-L)/2; if(ql<=M) update(o<<1,ql,qr,L,M); if(M<qr) update(o<<1|1,ql,qr,M+1,R); push_up(o,L,R); } } int query() { push_down(1,1,n); return maxu[1]; } }; Line_Tree tree; int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); scanf("%s",str+1); tree.build(1,1,n); char p[10]; while(m--) { scanf("%s",p); if(p[0]==‘q‘) printf("%d\n",tree.query()); else { int a,b; scanf("%d%d",&a,&b); tree.update(1,a,b,1,n); } } printf("\n"); } return 0; }
HDU 2871 Memory Control
比较繁琐的线段树，基本考察了各种常见操作。
注意一点reset不要用build而要用update以避免超时。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define ll long long #define LEN 50010<<2 using namespace std; struct Line_Tree { //sum维护区间内最多的块数 //ltrtmaxt维护区间内最长空白块长度 //left维护该块左端点 //get二分查找第n个块，update填充和释放区内，include寻找占据元素k的块 int sum[LEN],left[LEN],right[LEN]; int lt[LEN],rt[LEN],maxt[LEN]; int cov[LEN],setv[LEN]; void fill_cov(int o,int a,int b,int c,int L,int R) { lt[o]=rt[o]=maxt[o]=a?0:R-L+1; left[o]=b; right[o]=c; cov[o]=a; } void push_down(int o,int L,int R) { if(cov[o]!=-1) { int M=L+(R-L)/2; fill_cov(o<<1,cov[o],left[o],right[o],L,M); fill_cov(o<<1|1,cov[o],left[o],right[o],M+1,R); cov[o]=-1; } if(setv[o]!=-1) { sum[o<<1]=setv[o]; sum[o<<1|1]=setv[o]; setv[o<<1]=setv[o<<1|1]=setv[o]; setv[o]=-1; } } void push_up(int o,int L,int R) { sum[o]=sum[o<<1]+sum[o<<1|1]; int m=R-L+1,M=L+(R-L)/2; if(lt[o<<1]==m-(m>>1)) lt[o]=lt[o<<1]+lt[o<<1|1]; else lt[o]=lt[o<<1]; if(rt[o<<1|1]==(m>>1)) rt[o]=rt[o<<1]+rt[o<<1|1]; else rt[o]=rt[o<<1|1]; maxt[o]=max(rt[o<<1]+lt[o<<1|1],max(maxt[o<<1],maxt[o<<1|1])); } void build(int o,int L,int R) { lt[o]=rt[o]=maxt[o]=1; left[o]=right[o]=0; cov[o]=-1; setv[o]=-1; sum[o]=0; if(L==R) return ; else { int M=L+((R-L)>>1); build(o<<1,L,M); build(o<<1|1,M+1,R); push_up(o,L,R); } } //二分实现查找第k个块，返回该块左端点 int get(int o,int c,int L,int R) { if(L==R) return L; else { push_down(o,L,R); int M=L+((R-L)>>1); if(sum[o<<1]>=c) return get(o<<1,c,L,M); else return get(o<<1|1,c-sum[o<<1],M+1,R); } } //二分实现查找第一个空白长度大于c的区间左端点 int query(int o,int c,int L,int R) { if(L==R) return L; push_down(o,L,R); int M=L+((R-L)>>1); if(maxt[o<<1]>=c) return query(o<<1,c,L,M); else if(rt[o<<1]+lt[o<<1|1]>=c) return M-rt[o<<1]+1; else return query(o<<1|1,c,M+1,R); } //寻找含有k的数的左右端点 int include(int o,int k,int L,int R) { if(L==R) return o; int M=L+((R-L)>>1); push_down(o,L,R); if(k<=M) return include(o<<1,k,L,M); else return include(o<<1|1,k,M+1,R); } //实现填充与清空，a表示清空或填区间左端点 void update(int o,int a,int b,int c,int ql,int qr,int L,int R) { if(ql<=L&&R<=qr) fill_cov(o,a,b,c,L,R); else { push_down(o,L,R); int M=L+((R-L)>>1); if(ql<=M) update(o<<1,a,b,c,ql,qr,L,M); if(M<qr) update(o<<1|1,a,b,c,ql,qr,M+1,R); push_up(o,L,R); } } //实现对块的最左端点的清空与设置 void set(int o,int c,int ql,int qr,int L,int R) { if(ql<=L&&R<=qr) { sum[o]=c; setv[o]=c; } else { push_down(o,L,R); int M=L+((R-L)>>1); if(ql<=M) set(o<<1,c,ql,qr,L,M); if(M<qr) set(o<<1|1,c,ql,qr,M+1,R); push_up(o,L,R); } } }; Line_Tree tree; int main() { int n,m; // freopen("out.txt","w",stdout); while(scanf("%d%d",&n,&m)!=EOF) { char p[15]; int q; tree.build(1,1,n); while(m--) { scanf("%s",p); if(p[0]!=‘R‘) { scanf("%d",&q); if(p[0]==‘N‘) { if(tree.maxt[1]<q) puts("Reject New"); else { int pos=tree.query(1,q,1,n); printf("New at %d\n",pos); tree.update(1,1,pos,pos+q-1,pos,pos+q-1,1,n); tree.set(1,1,pos,pos,1,n); } } else if(p[0]==‘F‘) { int x,y,pos=tree.include(1,q,1,n); x=tree.left[pos]; y=tree.right[pos]; if(x) { printf("Free from %d to %d\n",x,y); tree.update(1,0,0,0,x,y,1,n); tree.set(1,0,x,x,1,n); } else puts("Reject Free"); } else if(p[0]==‘G‘) { if(q>tree.sum[1]) puts("Reject Get"); else { int pos=tree.get(1,q,1,n); printf("Get at %d\n",pos); } } } else { tree.update(1,0,0,0,1,n,1,n); tree.set(1,0,1,n,1,n); puts("Reset Now"); } } printf("\n"); } return 0; }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。