[Luogu 3224] HNOI2012 永无乡

---

特别水一个平衡树题。

不认真的代价是调试时间指数增长。

我写的 SBT，因为 Treap 的 rand() 实在写够了。

用并查集维护这些点的关系，然后启发式暴力合并，以及找第 \(k\) 小。

就是把子树较小的并到较大的里，一个一个点插入。

因为要插入新的点，给 SBT 预留的空间要大一些。（我试过只改变原来的点的信息，结果失败了。）

SBT 需要开的空间为 \(MAXN+MAXM\)，因为 \(n\) 个点，每个点最多被插入 \(m\) 次。

就这样。

表白一万次 SBT 的 Maintain 操作代码，超优美的qwq。

#include 
    
     #include 
     
      #include 
      
       using std::swap;const int MAXN=100010,MAXM=400010;int n,m,q;class UFS{    public:        void Init(int i)        {            f[i]=i;        }        int Find(int x)        {            return x==f[x] ? f[x] : f[x]=Find(f[x]);        }        void Merge(int x,int y)        {            f[Find(y)]=Find(x);        }    private:        int f[MAXN];}S;class SBT{    public:        SBT(int cnt=0):cnt(cnt){}        void Init(void)        {            for(int i=1,x;i<=n;++i)            {                scanf("%d",&x);                S.Init(i),s[rt[i]=++cnt]=node(x,i,1);            }        }        void Bridge(int x,int y)        {            int a=S.Find(x),b=S.Find(y);            if(a==b)                return;            if(s[rt[a]].size>s[rt[b]].size)                S.Merge(a,b),Merge(rt[a],b);            else                S.Merge(b,a),Merge(rt[b],a);        }        int FindKth(int x,int k)        {            return k>s[x=rt[S.Find(x)]].size ? -1 : Find(x,k);        }    private:        int cnt,rt[MAXN];        struct node        {            int v,num,size,c[2];            node(int v=0,int num=0,int size=0):v(v),num(num),size(size)            {                memset(c,0,sizeof c);            }        }s[MAXM];        void Update(int i)        {            s[i].size=s[s[i].c[0]].size+s[s[i].c[1]].size+1;        }        void Rotate(int &i,bool p)        {            int t=s[i].c[!p];            s[i].c[!p]=s[t].c[p],s[t].c[p]=i;            Update(i),Update(i=t);        }        void Maintain(int &i,bool p)        {            int t=s[s[i].c[!p]].size;            if(t
       
        s[i].v;            Insert(s[i].c[t],x,num);            Maintain(i,t);        }        void Merge(int &x,int &y)        {            if(!y)                return;            Insert(x,s[y].v,s[y].num),Merge(x,s[y].c[0]),Merge(x,s[y].c[1]);        }        int Find(int i,int x)        {            int t;            while(x!=(t=s[s[i].c[0]].size+1))                if(x
       
      
     
    

谢谢阅读。