一道简单的 $\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; }
近期评论