「题解」「BalticOI2011」种树 Growing Trees

一道简单的 $\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$$

时空限制

题解

思路

发现这道题目要求我们维护数列，于是考虑使用数据结构。

首先用排除法：暴力、树状数组、线段树、$\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;
}