线段树的练习题。
对应 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;
}
近期评论