#107. 维护全序集

题目描述

这是一道模板题，其数据比「普通平衡树」更强。

如未特别说明，以下所有数据均为整数。

维护一个多重集 S SS ，初始为空，有以下几种操作：

把 x xx 加入 S SS
删除 S SS 中的一个 x xx，保证删除的 x xx 一定存在
求 S SS 中第 k kk 小
求 S SS 中有多少个元素小于 x xx
求 S SS 中小于 x xx 的最大数
求 S SS 中大于 x xx 的最小数

操作共 n nn 次。

输入格式

第一行一个整数 n nn，表示共有 n nn 次操作。

接下来 n nn 行，每行为以下几种格式之一：

0 x，把 x xx 加入 S SS
1 x，删除 S SS 中的一个 x xx，保证删除的数在 S SS 中一定存在
2 k，求 S SS 中第 k kk 小的数，保证要求的数在 S SS 中一定存在
3 x，求 S SS 中有多少个数小于 x xx
4 x，求 S SS 中小于 x xx 的最大数，如果不存在，输出 −1 -1−1
5 x，求 S SS 中大于 x xx 的最小数，如果不存在，输出 −1 -1−1

输出格式

对于每次询问，输出单独一行表示答案。

样例

样例输入

样例输出

4

0

数据范围与提示

1≤n≤3×105,0≤x≤109 1 \leq n \leq 3 \times 10 ^ 5, 0 \leq x \leq 10 ^ 91≤n≤3×105,0≤x≤109

#include<iostream>

#include<cstdio>

#include<cstring>

#define INF 0x7fffffff

#define maxn 400010

using namespace std;

int m,rt,son[maxn][],fa[maxn],val[maxn],cnt[maxn],sz[maxn],size;

void update(int x){

    sz[x]=sz[son[x][]]+sz[son[x][]]+cnt[x];

}

void rotate(int x,int &k){

    int y=fa[x],z=fa[fa[x]],l,r;

    if(son[y][]==x)l=;else l=;r=l^;

    if(y==k)k=x;

    else son[z][son[z][]==y]=x;

    fa[x]=z;fa[y]=x;fa[son[x][r]]=y;

    son[y][l]=son[x][r];son[x][r]=y;

    update(y);update(x);

}

void splay(int x,int &k){

    while(x!=k){

        int y=fa[x],z=fa[fa[x]];

        if(y!=k){

            if((son[z][]==y)^(son[y][]==x))rotate(x,k);

            else rotate(y,k);

        }

        rotate(x,k);

    }

}

void Insert(int v){

    int y=,k=rt;

    while(k&&val[k]!=v)y=k,k=son[k][v>val[k]];

    if(k)cnt[k]++;

    else {

        k=++size;

        cnt[k]=sz[k]=;

        fa[k]=y;val[k]=v;

        if(y)son[y][v>val[y]]=k;

    }

    splay(k,rt);

}

int find2(int x){

    x++;int k=rt;

    if(sz[k]<x)return ;

    while(){

        if(sz[son[k][]]<x&&sz[son[k][]]+cnt[k]>=x)return k;

        if(sz[son[k][]]>=x)k=son[k][];

        else x-=sz[son[k][]]+cnt[k],k=son[k][];

    }

    return k;

}

void find1(int x){

    int k=rt;if(!k)return;

    while(son[k][x>val[k]]&&val[k]!=x)

        k=son[k][x>val[k]];

    splay(k,rt);

}

int nxt(int x,int f){

    find1(x);//if(!rt)return 0;

    if((val[rt]>x&&f)||(val[rt]<x&&!f))return rt;

    int k=son[rt][f];

    while(son[k][f^])k=son[k][f^];

    return k;

}

void del(int v){

    find1(v);

    int x=rt,k;

    if(cnt[rt]>){cnt[rt]--;sz[rt]--;return;}

    if(son[rt][]*son[rt][]==){

        rt=son[rt][]+son[rt][];

    }

    else {

        k=son[rt][];

        while(son[k][])k=son[k][];sz[k]+=sz[son[x][]];

        fa[son[x][]]=k;

        son[k][]=son[x][];rt=son[x][];

    }

    fa[rt]=;splay(k,rt);

}

void debug(){

    printf("%d ",val[rt]);

}

int main(){

    scanf("%d",&m);

    Insert(0x7fffffff);Insert(-0x7fffffff);

    int op,x;

    while(m--){

        scanf("%d%d",&op,&x);

        if(op==)Insert(x);

        if(op==)del(x);

        if(op==)printf("%d\n",val[find2(x)]);

        if(op==){

            find1(x);

            int ans=sz[son[rt][]]-;

            if(val[rt]<x)ans+=cnt[rt];

            printf("%d\n",ans);

        }

        if(op==){

            int w=val[nxt(x,)];

            if(w==INF||w==-INF)puts("-1");

            else printf("%d\n",w);

        }

        if(op==){

            int w=val[nxt(x,)];

            if(w==INF||w==-INF)puts("-1");

            else printf("%d\n",w);

        }

    }

    return ;

}

巴特西

loj #107. 维护全序集