一道简单的 $\texttt{splay}$ 题目。
题目链接：Luogu P4666/LibreOJ 2630/BalticOI 2011 D1T1。
当年比赛的官网链接（已挂）：https://www.boi2011.dk/ 。
题目
题目描述
给出一个长度为 $N$ 的数组 $a$，数组中每个数的取值范围均为 $[1,N]$。 接下来有 $M$ 组操作，操作分为两种：
- $\texttt{F}\quad\texttt{c}\quad\texttt{h}$
将满足 $a_i\geq h$ 的所有 $a_i$ 中最小的 $c$ 个数都 $+1$； - $\texttt{C}\quad\texttt{max}\quad\texttt{min}$
输出满足 $\texttt{min}\leq a_i\leq\texttt{max}$ 的个数。
数据范围
$$1\leq n,m\leq 10^5$$
时空限制
| 题目 | 时间限制 | 空间限制 |
|---|---|---|
| Luogu P4666 | $$1\text{s}$$ | $$250\text{MiB}$$ |
| LibreOJ 2630 | $$1\text{s}$$ | $$256\text{MiB}$$ |
| BalticOI 2011 D1T1 | $$1\text{s}$$ | $$256\text{MiB}$$ |
题解
思路
发现这道题目要求我们维护数列，于是考虑使用数据结构。
首先用排除法：暴力、树状数组、线段树、$\texttt{splay}$。
我们发现 $\texttt{splay}$ 可以解决这道题目，下面就介绍一下如何用 $\texttt{splay}$ 解决这道题目。
操作一
$$\texttt{F}\quad\texttt{c}\quad\texttt{h}$$
将满足 $a[i]\geq h$ 的所有 $a[i]$ 中最小的 $c$ 个数都 $+1$；
考虑找到 $\texttt{splay}$ 中权值为 $h$ 的位置，旋转到根，再从左子树中找到排名为 $c$ 的位置，（如果左子树大小小于 $c$ 则对左子树大小取 $\min$）。再修改 $\text{tag}$即可。
操作二
$$\texttt{C}\quad\texttt{max}\quad\texttt{min}$$
输出满足 $\texttt{min}\leq a[i]\leq\texttt{max}$ 的个数。
找到 $\texttt{min}$ 的位置，旋转到根，再把 $\texttt{max}$ 转到根的右节点，统计根节点的右节点的左子树大小即为答案。
细节
另外，注意一些细节，记得插入哨兵节点（正负无穷），同时记得把不存在的节点的内部最大值（查询时用）设为 $-\infty$（我就被这里卡了）。
代码
$\texttt{splay}$ 的渐近时间复杂度为 $\Theta(n\log_2n)$，可以通过。
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X3F3F3F3F //定义正无穷
#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 MAXN=100000+100;
inline void Read(void);
inline void Work(void);
int main(void){
Read();
Work();
return 0;
}
int n,m;
int a[MAXN];
inline void Read(void){
n=read(),m=read(); // 读入 n,m
for(reg int i=1;i<=n;++i)
a[i]=read(); //读入 a[]
return;
}
struct Splay{ //Splay
int root;
int val[MAXN],Max[MAXN],tag[MAXN];
int fa[MAXN],ch[MAXN][2];
int size[MAXN];
inline bool get(const int& x){
return x==ch[fa[x]][1];
}
inline void pushup(const int& ID){
Max[ID]=max(val[ID],max(Max[ch[ID][0]],Max[ch[ID][1]]));
size[ID]=size[ch[ID][0]]+size[ch[ID][1]]+1;
return;
}
inline int Build(const int& father,const int& l,const int& r,reg int a[]){
if(l>r)
return 0;
int mid=(l+r)>>1;
val[mid]=Max[mid]=a[mid];
fa[mid]=father;
size[mid]=1;
ch[mid][0]=Build(mid,l,mid-1,a);
ch[mid][1]=Build(mid,mid+1,r,a);
pushup(mid);
return mid;
}
inline void rotate(const int& x){
int f=fa[x],ff=fa[f];
reg bool wh=get(x);
if(ff)
ch[ff][get(f)]=x;
fa[f]=x;
ch[f][wh]=ch[x][wh^1];
if(ch[f][wh])
fa[ch[f][wh]]=f;
fa[x]=ff;
ch[x][wh^1]=f;
pushup(f);
pushup(x);
return;
}
inline void add(const int& ID,const int& Val){
val[ID]+=Val,Max[ID]+=Val,tag[ID]+=Val;
return;
}
inline void pushdown(const int& ID){
if(tag[ID]){
if(ch[ID][0])
add(ch[ID][0],tag[ID]);
if(ch[ID][1])
add(ch[ID][1],tag[ID]);
tag[ID]=0;
}
return;
}
inline void push(const int& x){
if(fa[x])
push(fa[x]);
pushdown(x);
return;
}
inline void splay(const int& x,const int& goal){
push(x);
for(int qwq;(qwq=fa[x])!=goal;rotate(x)){
if(fa[qwq]!=goal){
rotate(get(x)==get(qwq)?qwq:x);
}
}
if(goal==0)
root=x;
return;
}
inline int find(const int& x){
int now=root,res=0;
while(true){
pushdown(now);
if(x<=Max[ch[now][0]])
now=ch[now][0];
else{
res+=size[ch[now][0]];
if(x<=val[now])
return res+1;
++res;
now=ch[now][1];
}
}
return -1;
}
inline int kth(reg int x){
int now=root;
while(true){
pushdown(now);
if(x<=size[ch[now][0]])
now=ch[now][0];
else{
x-=size[ch[now][0]];
if(x==1){
splay(now,0);
return now;
}
--x;
now=ch[now][1];
}
}
return -1;
}
inline int split(const int& l,const int& r){ //把 l,r 旋转到根、根的右儿子
int x=kth(l),y=kth(r+2);
splay(x,0),splay(y,x);
return y;
}
inline void F(const int& c,const int& h){ //题目中的操作一
int l=find(h)-1,r=min(n,l+c-1);
if(l>n)
return;
int mid=find(val[kth(r+1)])-1,tr=ch[split(mid,r)][0];
fa[tr]=ch[fa[tr]][0]=0;
++tag[tr],++val[tr],++Max[tr]; //统计信息
if(mid>l){
reg int now=ch[split(l,mid-1)][0];
++tag[now],++val[now],++Max[now];
}
int p=find(val[tr])-1,u=split(p,p-1);
fa[tr]=u,ch[u][0]=tr;
splay(tr,0);
return;
}
inline int C(const int& Max,const int& Min){ //操作二
int l=find(Max)-1,r=find(Min+1)-2; //先旋转，记得不要忘了哨兵节点对编号的影响
return size[ch[split(l,r)][0]]; //返回答案
}
};
Splay S;
inline void Work(void){
S.Max[0]=-INF; //注意细节
a[n+1]=-INF,a[n+2]=INF; //插入哨兵节点
sort(a+1,a+n+3); //排序
S.root=S.Build(0,1,n+2,a); //建树
while(m--){
static char opt;
static int c,h,max,min;
do
opt=getchar();
while(opt!='F'&&opt!='C');
switch(opt){
case 'F':{
c=read(),h=read();
S.F(c,h);
break;
}
case 'C':{
max=read(),min=read();
printf("%d\n",S.C(max,min));
break;
}
default:break;
}
}
return;
}
近期评论