题目描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

1. 插入数值x。
2. 删除数值x(若有多个相同的数，应只删除一个)。
3. 查询数值x的排名(若有多个相同的数，应输出最小的排名)。
4. 查询排名为x的数值。
5. 求数值x的前驱(前驱定义为小于x的最大的数)。
6. 求数值x的后继(后继定义为大于x的最小的数)。

输入格式
第一行为n，表示操作的个数。
接下来n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)。

输出格式
对于操作3,4,5,6每行输出一个数，表示对应答案。

数据范围
$n \le 100000$,所有数均在$-10^7$到$10^7$内。

样例

输入样例：
8
1 10
1 20
1 30
3 20
4 2
2 10
5 25
6 -1
输出样例：
2
20
20
20

Splay树

Splay树

Vector+STL二分精简代码

#include <bits/stdc++.h>
using namespace std;
vector<int> a;
int n,opt,x;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    while(n--)
    {
        cin>>opt>>x;
        if (opt==1)
            a.insert(upper_bound(a.begin(),a.end(),x),x);
        if (opt==2)
            a.erase(lower_bound(a.begin(),a.end(),x));
        if (opt==3)
            cout<<lower_bound(a.begin(),a.end(),x)-a.begin()+1<<endl;
        if (opt==4)
            cout<<a[x-1]<<endl;
        if (opt==5)
            cout<<*--lower_bound(a.begin(),a.end(),x)<<endl;
        if (opt==6)
            cout<<*upper_bound(a.begin(),a.end(),x)<<endl;
    }
}
以下为Splay代码

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=201000;
struct splay_tree
{
    int ff,cnt,ch[2],val,size;
} t[N];
int root,tot;
void update(int x)
{
    t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt;
}
void rotate(int x)
{
    int y=t[x].ff;
    int z=t[y].ff;
    int k=(t[y].ch[1]==x);
    t[z].ch[(t[z].ch[1]==y)]=x;
    t[x].ff=z;
    t[y].ch[k]=t[x].ch[k^1];
    t[t[x].ch[k^1]].ff=y;
    t[x].ch[k^1]=y;
    t[y].ff=x;
    update(y);update(x);
}
void splay(int x,int s)
{
    while(t[x].ff!=s)
    {
        int y=t[x].ff,z=t[y].ff;
        if (z!=s)
            (t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y);
        rotate(x);
    }
    if (s==0)
        root=x;
}
void find(int x)
{
    int u=root;
    if (!u)
        return ;
    while(t[u].ch[x>t[u].val] && x!=t[u].val)
        u=t[u].ch[x>t[u].val];
    splay(u,0);
}
void insert(int x)
{
    int u=root,ff=0;
    while(u && t[u].val!=x)
    {
        ff=u;
        u=t[u].ch[x>t[u].val];
    }
    if (u)
        t[u].cnt++;
    else
    {
        u=++tot;
        if (ff)
            t[ff].ch[x>t[ff].val]=u;
        t[u].ch[0]=t[u].ch[1]=0;
        t[tot].ff=ff;
        t[tot].val=x;
        t[tot].cnt=1;
        t[tot].size=1;
    }
    splay(u,0);
}
int Next(int x,int f)
{
    find(x);
    int u=root;
    if (t[u].val>x && f)
        return u;
    if (t[u].val<x && !f)
        return u;
    u=t[u].ch[f];
    while(t[u].ch[f^1])
        u=t[u].ch[f^1];
    return u;
}
void Delete(int x)
{
    int last=Next(x,0);
    int Net=Next(x,1);
    splay(last,0);
    splay(Net,last);
    int del=t[Net].ch[0];
    if (t[del].cnt>1)
    {
        t[del].cnt--;
        splay(del,0);
    }
    else
        t[Net].ch[0]=0;
}
int kth(int x)
{
    int u=root;
    while(t[u].size<x)
        return 0;
    while(1)
    {
        int y=t[u].ch[0];
        if (x>t[y].size+t[u].cnt)
        {
            x-=t[y].size+t[u].cnt;
            u=t[u].ch[1];
        }
        else if (t[y].size>=x)
            u=y;
        else
            return t[u].val;
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    insert(1e9);
    insert(-1e9);
    while(n--)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        if (opt==1)
            insert(x);
        if (opt==2)
            Delete(x);
        if (opt==3)
        {
            find(x);
            printf("%d\n",t[t[root].ch[0]].size);
        }
        if (opt==4)
            printf("%d\n",kth(x+1));
        if (opt==5)
            printf("%d\n",t[Next(x,0)].val);
        if (opt==6)
            printf("%d\n",t[Next(x,1)].val);
    }
    return 0;
}
/*
插入数值x。
删除数值x(若有多个相同的数，应只删除一个)。
查询数值x的排名(若有多个相同的数，应输出最小的排名)。
查询排名为x的数值。
求数值x的前驱(前驱定义为小于x的最大的数)。
求数值x的后继(后继定义为大于x的最小的数)。
*/