线段树的练习题。
对应 OJ 的传送门。
《高手训练》解题报告集合:信息学奥赛一本通·高手训练。
线段树
线段树是一种优秀的维护序列的数据结构,支持所有满足结合律的操作的维护。
字符串排序 string
时空限制:\(3\texttt{s},256\texttt{MiB}\)。
题目描述
给定一个由小写字母组成的字符串 \(S\)。有 \(m\) 次操作,每次操作给定 \(3\) 个参数 \(l,r,x\)。如果 \(x=1\),将 \(S_l\sim S_r\) 升序排序;如果 \(x=0\),将 \(S_l\sim S_r\) 降序排序。你需要求出最终序列。
数据范围
对于 \(100\%\) 的数据,\(n,m\leq 10^5\)。
题解
线段树套路题,用线段树维护区间修改和区间查询,时间复杂度为 \(\Theta(|S|n\log_2n)\),其中 \(|S|\) 代表字符集大小,即 \(|S|=26\)。
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; inline int read(void){ reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return res; } const int MAXN=1e5+5; int n,m; char str[MAXN]; namespace SegmentTree{ #define lson ( (k) << 1 ) #define rson ( (k) << 1 | 1 ) #define mid ( ( (l) + (r) ) >> 1 ) struct Node{ int T[26]; int tag; #define T(x) unit[(x)].T #define tag(x) unit[(x)].tag }; Node unit[MAXN<<2]; inline void pushup(reg int k){ for(reg int i=0;i<26;++i) T(k)[i]=T(lson)[i]+T(rson)[i]; return; } inline void build(reg int k,reg int l,reg int r,reg char str[]){ tag(k)=-1; if(l==r){ ++T(k)[str[l]-'a']; return; } build(lson,l,mid,str),build(rson,mid+1,r,str); pushup(k); return; } inline void set(reg int k,reg int l,reg int r,reg int val){ for(reg int i=0;i<26;++i) T(k)[i]=0; T(k)[val]=r-l+1; tag(k)=val; return; } inline void pushdown(reg int k,reg int l,reg int r){ if(tag(k)!=-1){ set(lson,l,mid,tag(k)); set(rson,mid+1,r,tag(k)); tag(k)=-1; } return; } inline void update(reg int k,reg int l,reg int r,reg int L,reg int R,reg int val){ if(L<=l&&r<=R){ set(k,l,r,val); return; } pushdown(k,l,r); if(L<=mid) update(lson,l,mid,L,R,val); if(R>mid) update(rson,mid+1,r,L,R,val); pushup(k); return; } inline Node query(reg int k,reg int l,reg int r,reg int L,reg int R){ if(L<=l&&r<=R) return unit[k]; pushdown(k,l,r); if(L<=mid&&mid<R){ Node le=query(lson,l,mid,L,R),ri=query(rson,mid+1,r,L,R); for(reg int i=0;i<26;++i) le.T[i]+=ri.T[i]; return le; } else if(L<=mid) return query(lson,l,mid,L,R); else return query(rson,mid+1,r,L,R); } inline void print(reg int k,reg int l,reg int r){ if(l==r){ for(reg int i=0;i<26;++i) if(T(k)[i]){ putchar('a'+i); break; } return; } pushdown(k,l,r); print(lson,l,mid),print(rson,mid+1,r); return; } #undef lson #undef rson #undef mid } using namespace SegmentTree; int main(void){ n=read(),m=read(); scanf("%s",str+1); build(1,1,n,str); while(m--){ static int l,r,x; static Node tmp; l=read(),r=read(),x=read(); if(x==1){ tmp=query(1,1,n,l,r); reg int lptr=l; for(reg int i=0;i<26;++i) if(tmp.T[i]){ update(1,1,n,lptr,lptr+tmp.T[i]-1,i); lptr+=tmp.T[i]; } } else{ tmp=query(1,1,n,l,r); reg int rptr=r; for(reg int i=0;i<26;++i) if(tmp.T[i]){ update(1,1,n,rptr-tmp.T[i]+1,rptr,i); rptr-=tmp.T[i]; } } } print(1,1,n); putchar('\n'); return 0; }
纪念碑 square
时空限制:\(3\texttt{s},256\texttt{MiB}\)。
题目描述
2034 年,某中学决定修建校庆 100 周年纪念碑,作为杰出校友的你被找了过来,帮校方确定纪念碑的选址.中学的土地可以看作是一个长为 \(n\),宽为 \(m\) 的矩形。它由 \(n\times m\) 个 \(1\times 1\) 的正方形组成,其中左下角的正方形的坐标为 \((1,1)\),右上角的正方形的坐标为 \((n,m)\)。其中有一些土地已经被用来修建建筑物,每一幢建筑物都可以看做是一个左下角为 \((x_1,y_1)\),右上角为 \((x_2,y_2)\) 的矩形。纪念碑可以看作是一个正方形。校方希望你找出一块最大的正方形区域供他们参考。
数据范围
对于 \(100\%\) 的数据,\(p\leq 4\times 10^5\),\(m,n\leq 10^6\)。
题解
扫描线的题。
考虑用线段树维护 \(y\) 轴最长空位长度,并用双指针来维护 \(x\) 轴坐标长度,当 \(y\) 轴坐标长度小于 \(x\) 坐标长度时,左指针右移。
时间复杂度为 \(\Theta(n\log_2m)\)。
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return res; } const int MAXN=1e6+5; struct Node{ int l,r; inline Node(reg int l=0,reg int r=0):l(l),r(r){ return; } }; namespace SegmentTree{ #define lson ( (k) << 1 ) #define rson ( (k) << 1 | 1 ) #define mid ( ( (l) + (r) ) >> 1 ) struct Node{ int len; int lMax,rMax,Max; int tag; #define len(x) unit[(x)].len #define lMax(x) unit[(x)].lMax #define rMax(x) unit[(x)].rMax #define Max(x) unit[(x)].Max #define tag(x) unit[(x)].tag }; Node unit[MAXN<<2]; inline void build(reg int k,reg int l,reg int r){ len(k)=lMax(k)=rMax(k)=Max(k)=r-l+1; if(l==r) return; build(lson,l,mid),build(rson,mid+1,r); return; } inline void update(reg int k){ if(tag(k)) lMax(k)=rMax(k)=Max(k)=0; else if(len(k)==1) lMax(k)=rMax(k)=Max(k)=1; else{ lMax(k)=(lMax(lson)==len(lson))?len(lson)+lMax(rson):lMax(lson); rMax(k)=(rMax(rson)==len(rson))?len(rson)+rMax(lson):rMax(rson); Max(k)=max(rMax(lson)+lMax(rson),max(Max(lson),Max(rson))); } return; } inline void update(reg int k,reg int l,reg int r,reg int L,reg int R,reg int val){ if(L<=l&&r<=R){ tag(k)+=val; update(k); return; } if(L<=mid) update(lson,l,mid,L,R,val); if(R>mid) update(rson,mid+1,r,L,R,val); update(k); return; } #undef lson #undef rson #undef mid } int n,m,p; vector<Node> add[MAXN],del[MAXN]; int main(void){ n=read(),m=read(),p=read(); for(reg int i=1;i<=p;++i){ static int x1,y1,x2,y2; x1=read(),y1=read(),x2=read(),y2=read(); add[x1].push_back(Node(y1,y2)); del[x2].push_back(Node(y1,y2)); } int ans=0; SegmentTree::build(1,1,m); for(reg int r=1,l=1;r<=n;++r){ for(reg int i=0,siz=add[r].size();i<siz;++i) SegmentTree::update(1,1,m,add[r][i].l,add[r][i].r,1); ans=max(ans,min(SegmentTree::unit[1].Max,r-l+1)); while(r-l+1>SegmentTree::unit[1].Max){ for(reg int i=0,siz=del[l].size();i<siz;++i) SegmentTree::update(1,1,m,del[l][i].l,del[l][i].r,-1); ++l; } } printf("%d\n",ans); return 0; }
区间连通性 interval
时空限制:\(1\texttt{s},256\texttt{MiB}\)。
题目描述
对于两个区间 \((a,b)\) 和 \((c,d)\),若 \(c<a<d\) 或 \(c<b<d\),则可以从 \((a,b)\) 走到 \((c,d)\),现在有以下两种操作:
- \(1\) \(x\) \(y\)(\(x<y\)),表示在区间集合中添加 \((x,y)\) 这个区间,保证新加入的这个区间长度一定比之前的所有区间长度长。
- \(2\) \(a\) \(b\)(\(a\ne b\)),表示询问是否存在一条路径能从第 \(a\) 个区间走到第 \(b\) 个区间。
初始时区间集合为空,现在请你来回答所有的询问。
数据范围
对于 \(100\%\) 的数据,\(1\leq n\leq 10^5\),区间端点在 \(32\) 位有符号整数范围内。
题解
如果区间 \(A\) 可以到 \(B\) 且 \(|A|\geq |B|\),那么显然 \(B\) 可以到 \(A\),这说明初期的连通关系是无向的。
我们不妨用并查集来维护这种无向连通关系,如果两个区间在同一个连通块内(可以互相到达),那么它们在并查集中同属一个集合。
考虑到区间长度单调递增,那么如果存在区间 \([l,r]\) 满足当前加入区间 \((u,v)\) 有一个端点(\(u+1,v-1\))在 \([l,r]\) 内,那么它们必然可以相互到达,于是我们可以用线段树来维护这种简单的重叠关系。
具体的,我们线段树上的每一个节点上开一个 \(\texttt{vector}\),表示该节点代表区间上覆盖有的区间的编号的集合。我们每次直接查询当前区间两个端点在线段树上的对应区间,直接合并即可。最后删除之前的用过的区间,更新为与当前区间重合的所有区间的并,单次修改时间复杂度为 \(\Theta(\log_2n)\)。
考虑查询,则由于没有区间大小关系(可能 \(y\) 的代表集合 包含于 \(x\) 的代表集合,此时 \(x\) 不能到 \(y\) 但 \(y\) 可以到 \(x\)),我们应该直接根据题目的定义判定:
- \(x,y\) 属于同一个集合,显然可以相互到达。
- \(x\to y\),符合题意。
线段树单次查询的时间复杂度为 \(\Theta(\alpha(n))\)。
总的时间复杂度为 \(\Theta(n\log_2n)\)。
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; inline int read(void){ static int tmp; scanf("%d",&tmp); return tmp; } const int MAXN=2e5+5; struct Node{ int opt,l,r; inline Node(reg int opt=0,reg int l=0,reg int r=0):opt(opt),l(l),r(r){ return; } }; int n; Node a[MAXN]; vector<int> V; int fa[MAXN]; int le[MAXN],ri[MAXN]; inline int find(reg int x){ if(x==fa[x]) return x; else return fa[x]=find(fa[x]); } namespace SegmentTree{ #define lson ( (k) << 1 ) #define rson ( (k) << 1 | 1 ) #define mid ( ( (l) + (r) ) >> 1 ) struct Node{ vector<int> V; #define V(x) unit[(x)].V }; Node unit[MAXN<<2]; inline void merge(reg int k,reg int l,reg int r,reg int pos,reg int id){ for(reg int i=0,siz=V(k).size();i<siz;++i){ reg int rx=find(V(k)[i]),ry=find(id); fa[rx]=ry; le[ry]=min(le[ry],le[rx]); ri[ry]=max(ri[ry],ri[rx]); } V(k).clear(); if(l==r) return; if(pos<=mid) merge(lson,l,mid,pos,id); else merge(rson,mid+1,r,pos,id); return; } inline void update(reg int k,reg int l,reg int r,reg int L,reg int R,int id){ if(L==l&&r==R){ V(k).push_back(id); return; } if(R<=mid) update(lson,l,mid,L,R,id); else if(mid<L) update(rson,mid+1,r,L,R,id); else update(lson,l,mid,L,mid,id),update(rson,mid+1,r,mid+1,R,id); return; } #undef lson #undef rson #undef mid } int main(void){ n=read(); for(reg int i=1;i<=n;++i){ static int opt,l,r; opt=read(),l=read(),r=read(); a[i]=Node(opt,l,r); if(opt==1) V.push_back(l),V.push_back(r); } sort(V.begin(),V.end()); V.erase(unique(V.begin(),V.end()),V.end()); for(reg int i=1;i<=n;++i) if(a[i].opt==1){ a[i].l=lower_bound(V.begin(),V.end(),a[i].l)-V.begin()+1; a[i].r=lower_bound(V.begin(),V.end(),a[i].r)-V.begin()+1; } reg int m=V.size(); reg int tot=0; for(reg int i=1;i<=n;++i) if(a[i].opt==1){ ++tot; fa[tot]=tot; le[tot]=a[i].l,ri[tot]=a[i].r; SegmentTree::merge(1,1,m,a[i].l,tot); SegmentTree::merge(1,1,m,a[i].r,tot); reg int x=find(tot); if(le[x]+1<=ri[x]-1) SegmentTree::update(1,1,m,le[x]+1,ri[x]-1,tot); } else{ reg int x=a[i].l,y=a[i].r; reg int rx=find(x),ry=find(y); if(rx==ry||(le[ry]<le[rx]&&le[rx]<ri[ry])||(le[ry]<ri[rx]&&ri[rx]<ri[ry])) puts("YES"); else puts("NO"); } return 0; }
栈的维护 weed
时空限制:\(1\texttt{s},512\texttt{MiB}\)。
题目描述
从前有个栈,一开始是空的。
你写下了 \(m\) 个操作,每个操作形如 \(k\) \(v\),若 \(k=0\),代表往栈顶加入一个数 \(v\);若 \(k=1\),则代表从栈顶弹出 \(v\) 个数,如果栈中的元素少于 \(v\) 个,则全部弹出。
接着你又进行了 \(q\) 次修改,每次你会选择一个操作,并且修改它的两个参数。
在每次修改后,你都要求出如果依次执行这些操作,最后栈中剩下的元素之和。
数据范围
对于 \(100\%\) 的数据,\(m,q\leq 2\times 10^5\),\(v\leq 10^4\)。
题解
不难看出是线段树分治,即对时间建立线段树维护操作。
具体的,我们每个节点维护三个值:
- \(\texttt{add}\),表示经过这个区间之后增加的元素个数。如果一个元素在这个区间加入后删除,则它对 \(\texttt{add}\) 没有影响。
- \(\texttt{del}\),表示经过这个区间之后减少的元素个数。如果一个元素在这个区间加入后删除,则它对 \(\texttt{del}\) 没有影响。
- \(\texttt{sum}\),表示经过这个区间之后栈中剩余元素的和。
那么我们可以得出合并式:
- \(\texttt{add}_k=\max\{\texttt{add}_{\texttt{lson}}-\texttt{del}_{\texttt{rson}},0\}+\texttt{add}_{\texttt{rson}}\)
- \(\texttt{del}_k=\texttt{del}_{\texttt{lson}}+\max\{\texttt{del}_{\texttt{rson}}-\texttt{add}_{\texttt{lson}},0\}\)
- \(\texttt{sum}_k=\texttt{sum}_{\texttt{rson}}+\operatorname{query}(\texttt{lson},\texttt{del}_{\texttt{rson}})\)
时间复杂度为 \(\Theta(n\log_2n+m\log^2_2n)\)。
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg bool f=false; reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return f?-res:res; } const int MAXM=2e5+5; struct Operation{ int k,v; inline Operation(reg int k=0,reg int v=0):k(k),v(v){ return; } inline void Read(void){ k=read(),v=read(); return; } }; namespace SegmentTree{ #define lson ( (k) << 1 ) #define rson ( (k) << 1 | 1 ) #define mid ( ( (l) + (r) ) >> 1 ) struct Node{ int add,del; int sum; #define add(x) unit[(x)].add #define del(x) unit[(x)].del #define sum(x) unit[(x)].sum }; Node unit[MAXM<<2]; inline int query(reg int k,reg int val){ if(add(k)<=val) return 0; if(add(rson)>=val) return sum(k)-sum(rson)+query(rson,val); else return query(lson,val-add(rson)+del(rson)); } inline void pushup(reg int k){ del(k)=del(lson)+max(del(rson)-add(lson),0); add(k)=max(add(lson)-del(rson),0)+add(rson); sum(k)=sum(rson)+(del(rson)?query(lson,del(rson)):sum(lson)); return; } inline void build(reg int k,reg int l,reg int r,reg Operation a[]){ if(l==r){ if(a[l].k==1) del(k)=a[l].v,add(k)=sum(k)=0; else del(k)=0,add(k)=1,sum(k)=a[l].v; return; } build(lson,l,mid,a),build(rson,mid+1,r,a); pushup(k); return; } inline void update(reg int k,reg int l,reg int r,reg int pos,reg int K,reg int V){ if(l==r){ if(K==1) del(k)=V,add(k)=sum(k)=0; else del(k)=0,add(k)=1,sum(k)=V; return; } if(pos<=mid) update(lson,l,mid,pos,K,V); else update(rson,mid+1,r,pos,K,V); pushup(k); return; } #undef lson #undef rson #undef mid } int m,q; Operation O[MAXM]; int main(void){ m=read(),q=read(); for(reg int i=1;i<=m;++i) O[i].Read(); SegmentTree::build(1,1,m,O); while(q--){ static int c,k,v; c=read(),k=read(),v=read(); SegmentTree::update(1,1,m,c,k,v); printf("%d\n",SegmentTree::unit[1].sum); } return 0; }
星际探测 melancholy
时空限制:\(1\texttt{s},256\texttt{MiB}\)。
题目描述
DX3906 星系,Melancholy 星上,我在勘测这里的地质情况。
我把这些天来已探测到的区域分为 \(N\) 组,并用二元组 \((D,V)\) 对每一组进行标记:其中 \(D\) 为区域的相对距离,\(V\) 为内部地质元素的相对丰富程度。
在我的日程安排表上有 \(Q\) 项指派的计划。每项计划的形式是类似的,都是“对相对距离 \(D\) 在 \([L,R]\) 之间的区域进行进一步的勘测,并在其中有次序地挑出 \(K\) 块区域的样本进行研究。”采集这 \(K\) 块的样品后,在实验中它们的研究价值即为这 \(K\) 块区域地质相对丰富程度 \(V\) 的乘积。
我对这 \(Q\) 项计划都进行了评估:一项计划的评估值 \(P\) 为所有可能选取情况的研究价值之和。
但是由于仪器的原因,在一次勘测中,这其中 \(V\) 最小的区域永远不会被选取。
现在我只想知道这 \(Q\) 项计划的评估值对 \(2^{32}\) 取模后的值。特殊地,如果没有 \(K\) 块区域可供选择,评估值为 \(0\)。
数据范围
对于 \(100\%\) 的数据,\(1\leq K\leq 6\),\(1\leq N,Q\leq 10^5\),\(1\leq D,V\leq 10^9\),\(1\leq L\leq R\leq 10^9\)。
数据保证所有区域的 \(D\) 与 \(V\) 互不相等。
题解
显然可以合并答案。答案的合并式为
\[f_{k,i}=\sum^i_{j=0}f_{\texttt{lson},j}f_{\texttt{rson},i-j}\]
所以我们先用线段树维护区间,然后最后把查询区间根据最小值位置裂成两半,最后合并即可。值得注意的是,合并答案时的单位元为:
\[
f_i=
\begin{cases}
1,&i=0\\
0,&i\ne 0
\end{cases}
\]
对 \(2^{32}\) 取模直接自然溢出 unisigned int
即可。
时间复杂度为 \(\Theta(k^2n\log_2n)\)。
#include<bits/stdc++.h> using namespace std; #define reg register typedef unsigned int uint; typedef long long ll; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return res; } const int MAXN=1e5+5; const int MAXK=6+1; const uint inf=0x7fffffffu; struct Data{ uint d,v; inline Data(reg uint d=0,reg uint v=0):d(d),v(v){ return; } inline bool operator<(const Data& a)const{ return d<a.d; } }; int n,q; Data a[MAXN]; namespace SegmentTree{ #define lson ( (k) << 1 ) #define rson ( (k) << 1 | 1 ) #define mid ( ( (l) + (r) ) >> 1 ) struct Node{ int pos; uint f[MAXK]; inline Node(void){ pos=0,memset(f,0,sizeof(f)); f[0]=1; return; } inline Node operator+(const Node& x){ Node res; res.f[0]=0; if(a[pos].v<a[x.pos].v) res.pos=pos; else res.pos=x.pos; for(reg int i=0;i<MAXK;++i) for(reg int j=0;j<=i;++j) res.f[i]+=f[j]*x.f[i-j]; return res; } #define f(x) unit[(x)].f #define pos(x) unit[(x)].pos }; Node unit[MAXN<<2]; inline void pushup(reg int k){ unit[k]=unit[lson]+unit[rson]; return; } inline void build(reg int k,reg int l,reg int r,reg Data a[]){ if(l==r){ f(k)[1]=a[l].v; pos(k)=l; return; } build(lson,l,mid,a),build(rson,mid+1,r,a); pushup(k); return; } inline Node query(reg int k,reg int l,reg int r,reg int L,reg int R){ if(L<=l&&r<=R) return unit[k]; Node res; if(L<=mid) res=res+query(lson,l,mid,L,R); if(R>mid) res=res+query(rson,mid+1,r,L,R); return res; } #undef lson #undef rson #undef mid } uint fac[MAXN]; using namespace SegmentTree; int main(void){ n=read(),q=read(); a[0].v=inf; for(reg int i=1;i<=n;++i) a[i].d=read(); for(reg int i=1;i<=n;++i) a[i].v=read(); fac[0]=1; for(reg int i=1;i<=n;++i) fac[i]=fac[i-1]*i; sort(a+1,a+n+1); build(1,1,n,a); while(q--){ static int L,R,k; L=read(),R=read(),k=read(); reg int l=lower_bound(a+1,a+n+1,Data(L,0))-a; reg int r=upper_bound(a+1,a+n+1,Data(R,0))-(a+1); if(l>r||l>n) puts("0"); else{ reg int pos=query(1,1,n,l,r).pos; Node tmp; if(l<=pos-1) tmp=tmp+query(1,1,n,l,pos-1); if(r>=pos+1) tmp=tmp+query(1,1,n,pos+1,r); printf("%u\n",tmp.f[k]*fac[k]); } } return 0; }
近期评论