COGS 723. [SDOI2007] 超级数组

★★☆ 输入文件：arr.in 输出文件：arr.out 简单对比
时间限制：1 s 内存限制：4 MB

Source: SDOI2007 Day2
【问题描述】

一般的数组大家都经常使用，相信很多同学没有见过下面的超级数组。

超级数组存储的是一些正整数，它还支持下面的两个操作

(1)、插入一个元素，命令是 "i key" 。 key 是要插入的数。

(2)、输出第 k 大元素并删除该元素，命令是 "d k"。输出第 k 大元素并删除它。

“第 k 大”是指：现有的数中，如果从小到大排好序，从最小的开始作为第一大算起，

一直数到第 k 个。

现在给出一个开始是空的超级数组，请维护好该数组。

【输入】(arr.in)

第一行 n、m：n<=1 000 000 000 , m<=100 000。表示插入数的范围是 1 至n ,共有m 条

命令（包括插入和删除）。

以下 m 行，每行一条命令，如题中描述。每条命令中字母和后面的数字之间一个空格。

保证输入数据是正确的，删除的数一定存在。

【输出】（arr.out）

对于每个删除命令，按删除命令顺序输出删除的数，每个数一行

【样例输入】

100 10

i 57

i 99

i 65

d 3

i 89

d 2

d 1

i 93

i 29

【样例输出】

splay

屠龙宝刀点击就送

#include <cstdio>
#include <cctype>
#define N 105000
int data[N],cnt[N],siz[N],ch[N][2],fa[N],root,cn,n,m;
inline int son(int x) {return ch[fa[x]][1]==x;}
inline void read(int &x)
{
    register char ch=getchar();
    for(x=0;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);x=x*10+ch-'0',ch=getchar());
}
inline void pushup(int rt)
{
    int l=ch[rt][0],r=ch[rt][1];
    siz[rt]=siz[l]+siz[r]+cnt[rt];
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],b=son(x),c=son(y),a=ch[x][!b];
    if(z) ch[z][c]=x;
    else root=x;
    fa[x]=z;
    if(a) fa[a]=y;
    ch[y][b]=a;
    ch[x][!b]=y;
    fa[y]=x;
    pushup(y);
    pushup(x);
}
void splay(int x,int i)
{
    while(fa[x]!=i)
    {
        int y=fa[x],z=fa[y];
        if(z==i) rotate(x);
        else
        {
            if(son(x)==son(y)) rotate(y),rotate(x);
            else rotate(x),rotate(x);
        }
    }
}
void ins(int &rt,int x)
{
    if(!rt)
    {
        rt=++cn;
        data[cn]=x;
        cnt[cn]=siz[cn]=1;
        splay(cn,0);
        return;
    }
    if(data[rt]==x)
    {
        cnt[rt]++;
        siz[rt]++;
        splay(rt,0);
        return;
    }
    if(x<data[rt])
    {
        ins(ch[rt][0],x);
        fa[ch[rt][0]]=rt;
        pushup(rt);
    }
    else
    {
        ins(ch[rt][1],x);
        fa[ch[rt][1]]=rt;
        pushup(rt);
    }
}
int getkth(int rt,int k)
{
    int l=ch[rt][0];
    if(siz[l]+1<=k&&k<=siz[l]+cnt[rt]) return rt;
    if(siz[l]+1>k) return getkth(ch[rt][0],k);
    if(cnt[rt]+siz[l]<k) k-=siz[l]+cnt[rt],getkth(ch[rt][1],k);
}
int getmn(int rt)
{
    int ret=-1,p=rt;
    while(p)
    {
        ret=p;
        p=ch[p][0];
    }
    return ret;
}
void del(int rt,int x)
{
    if(data[rt]==x)
    {
        if(cnt[rt]>1)
        {
            siz[rt]--;
            cnt[rt]--;
        }
        else
        {
            splay(rt,0);
            int p=getmn(ch[rt][1]);
            if(p!=-1)
            {
                splay(p,rt);
                root=p;fa[p]=0;
                ch[p][0]=ch[rt][0];
                fa[ch[rt][0]]=p;
            }
            else
            {
                root=ch[rt][0];
                fa[ch[rt][0]]=0;
            }
        }
        return;
    }
    if(x<data[rt])
    {
        del(ch[rt][0],x);
        pushup(rt);
    }
    else
    {
        del(ch[rt][1],x);
        pushup(rt);
    }
}
int Main()
{
    freopen("arr.in","r",stdin);
    freopen("arr.out","w",stdout);
    read(n);read(m);
    char str[5];
    for(int k;m--;)
    {
        scanf("%s",str);
        read(k);
        if(str[0]=='i') ins(root,k);
        else
        {
            int x=data[getkth(root,k)];
            printf("%d
",x);
            del(root,x);
        }
    }
    return 0;
}
int sb=Main();
int main(int argc,char *argv[]){;}