问题描述:

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
1. 插入x数
2. 删除x数(若有多个相同的数,因只删除一个)
3. 查询x数的排名(若有多个相同的数,因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x,且最大的数)
6. 求x的后继(后继定义为大于x,且最小的数)

输入:

第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号。

输出:

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

思路:

模板题,也没什么好说的呢。

代码:

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;

int n, ans, tot, root;

struct Treap {int l, r, val, rank, cnt, size;} t[MAXN];

void update(int p)
{
    t[p].size=t[t[p].l].size+t[t[p].r].size+t[p].cnt;
}

int findrank(int p, int val)
{
    if(p==0) return 0;
    if(val==t[p].val) return t[t[p].l].size+1;
    if(val<t[p].val) return findrank(t[p].l, val);
    return findrank(t[p].r, val)+t[t[p].l].size+t[p].cnt;
}

int findval(int p, int rank)
{
    if(p==0) return 0;
    if(t[t[p].l].size>=rank) return findval(t[p].l, rank);
    if(t[t[p].l].size+t[p].cnt>=rank) return t[p].val;
    return findval(t[p].r, rank-t[t[p].l].size-t[p].cnt);
}

void zig(int &p)
{
    int q=t[p].l;
    t[p].l=t[q].r; t[q].r=p; p=q;
    update(t[p].r); update(p);
}

void zag(int &p)
{
    int q=t[p].r;
    t[p].r=t[q].l; t[q].l=p; p=q;
    update(t[p].l); update(p);
}

void insert(int &p, int val)
{
    if(p==0)
    {
        t[++tot].val=val; t[tot].rank=rand();
        t[tot].cnt=t[tot].size=1; p=tot;
        return;
    }
    if(val==t[p].val) t[p].cnt++;
    if(val<t[p].val)
    {
        insert(t[p].l, val);
        if(t[p].rank<t[t[p].l].rank) zig(p);
    }
    if(val>t[p].val)
    {
        insert(t[p].r, val);
        if(t[p].rank<t[t[p].r].rank) zag(p);
    }
    update(p);
}

void remove(int &p, int val)
{
    if(p==0) return;
    if(val==t[p].val)
    {
        if(t[p].cnt>1)
        {
            t[p].cnt--;  update(p);
            return;
        }
        if(t[p].l*t[p].r==0) p=t[p].l+t[p].r;
        else if(t[t[p].l].rank>t[t[p].r].rank) zig(p), remove(p, val);
        else zag(p), remove(p, val);
    }
    if(val<t[p].val) remove(t[p].l, val);
    if(val>t[p].val) remove(t[p].r, val);
    update(p);
}

void findpre(int p, int x)
{
    if(p==0) return;
    if(t[p].val<x) ans=p, findpre(t[p].r, x);
    else findpre(t[p].l, x);
}

void findnext(int p, int x)
{
    if(p==0) return;
    if(t[p].val>x) ans=p, findnext(t[p].l,x);
    else findnext(t[p].r,x);
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if(opt==1) insert(root, x);
        if(opt==2) remove(root, x);
        if(opt==3) printf("%d\n", findrank(root, x));
        if(opt==4) printf("%d\n", findval(root, x));
        if(opt==5) ans=0, findpre(root, x), printf("%d\n", t[ans].val);
        if(opt==6) ans=0, findnext(root, x), printf("%d\n", t[ans].val);
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注