1. 题目

传送门＝￣ω￣＝

2. 题解

这题调了我好久好久啊！
其实就一模板题，用来学 Treap。。。
一开始写的指针树，都不知道飞到哪里去了
后来写了个数组的但是超级辣鸡，数组都能段错误。。。
然后照着 hzwer 的代码改了一下，还是有错误。
最后无语了，自己重写了一份。
然而还是WA了一次。
仔细一看发现是求 kth 的时候把一个变量写错了。。。

真畸形
建议 treap 用静态数组写，虽然会浪费一些空间，但是理论上会快一些，而且可以设置节点 0 为不存在的节点，这样就不用每次判断一下是否存在这个节点防止段错误了。
如果你实在不想浪费空间就搞个空间回收栈即可。

代码：

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>void IN(_Tp&dig)
{
    char c=getchar();dig=0;bool flag=0;
    while(!isdigit(c)&&c!='-')c=getchar();
    if(c=='-')flag=1,c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
static const int maxs=100005;
struct treap
{
    int root,size,l[maxs],r[maxs],f[maxs],d[maxs],w[maxs],s[maxs];
    treap()//初始化
    {
        root=size=0;
        memset(l,0,sizeof(l)),memset(r,0,sizeof(r));
        memset(d,0,sizeof(d)),memset(w,0,sizeof(w));
        memset(s,0,sizeof(s));
    }
    void update(int a){s[a]=s[l[a]]+s[r[a]]+w[a];}//更新节点 size
    void lrot(int&a)//左旋
    {
        int b=r[a];
        r[a]=l[b],l[b]=a,s[b]=s[a],update(a),a=b;
    }
    void rrot(int&a)//右旋
    {
        int b=l[a];
        l[a]=r[b],r[b]=a,s[b]=s[a],update(a),a=b;
    }
    void insert(int&a,int data)//插入 data
    {
        if(!a)
        {
            size++,a=size;
            f[a]=rand(),d[a]=data,w[a]=s[a]=1;
            return;
        }
        s[a]++;
        if(d[a]==data)w[a]++;
        else if(data<d[a])
        {
            insert(l[a],data);
            if(f[l[a]]<f[a])rrot(a);
        }
        else
        {
            insert(r[a],data);
            if(f[r[a]]<f[a])lrot(a);
        }
    }
    void del(int&a,int data)//删除 data
    {
        if(!a)return;
        if(d[a]==data)
        {
            if(w[a]>1){w[a]--,s[a]--;return;}
            if(!l[a]||!r[a]){a=l[a]+r[a];return;}
            if(f[l[a]]<f[r[a]])rrot(a),del(a,data);
            else lrot(a),del(a,data);
            return;
        }
        s[a]--;
        if(data<d[a])del(l[a],data);
        else del(r[a],data);
    }
    int query_rank(int&a,int data)//求 data 的排序后的位置
    {
        if(!a)return 0;
        if(d[a]==data)return s[l[a]]+1;
        if(data<d[a])return query_rank(l[a],data);
        else return s[l[a]]+w[a]+query_rank(r[a],data);
    }
    int query_kth(int&a,int k)//求 kth
    {
        if(!a)return 0;
        if(k<=s[l[a]])return query_kth(l[a],k);
        if(k>s[l[a]]+w[a])return query_kth(r[a],k-s[l[a]]-w[a]);
        return d[a];
    }
    int query_pre(int&a,int data)//求前驱
    {
        if(!a)return INT_MIN;
        if(data<=d[a])return query_pre(l[a],data);
        return max(d[a],query_pre(r[a],data));
    }
    int query_nxt(int&a,int data)//求后驱
    {
        if(!a)return INT_MAX;
        if(data>=d[a])return query_nxt(r[a],data);
        return min(d[a],query_nxt(l[a],data));
    }
}t;
int n;
int main()
{
    IN(n),srand(n);
    for(int i=1,opt,x;i<=n;i++)
    {
        IN(opt),IN(x);
        switch(opt)
        {
            case 1:t.insert(t.root,x);break;
            case 2:t.del(t.root,x);break;
            case 3:printf("%d\n",t.query_rank(t.root,x));break;
            case 4:printf("%d\n",t.query_kth(t.root,x));break;
            case 5:printf("%d\n",t.query_pre(t.root,x));break;
            case 6:printf("%d\n",t.query_nxt(t.root,x));break;
            default:break;
        }
    }
    return 0;
}