jdoj 2183 普通平衡树

题目传送门

Description

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

#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;
struct your
{
    int l,r,v,rnd,w,s;
}a[200000];
int root,tot;
int aftr,befor;
void push(int k)
{
    a[k].s=a[k].w+a[a[k].l].s+a[a[k].r].s;
}
void lturn(int &k)
{
    int t=a[k].r;
    a[k].r=a[t].l;
    a[t].l=k;
    push(k);
    push(t);
    k=t;
}
void rturn(int &k)
{
    int t=a[k].l;
    a[k].l=a[t].r;
    a[t].r=k;
    push(k);
    push(t);
    k=t;
}
void update(int &k,int temp)
{
    if(!k)
    {
        k=++tot;
        a[k].w=a[k].s=1;
        a[k].v=temp;
        a[k].rnd=rand();
        return ;
    }
    a[k].s++;
    if(temp==a[k].v) a[k].w++;
    else if(temp<a[k].v)
    {
        update(a[k].l,temp);
        if(a[a[k].l].rnd<a[k].rnd) rturn(k);
    } 
    else
    {
        update(a[k].r,temp);
        if(a[a[k].r].rnd<a[k].rnd) lturn(k);
    }
}
void del(int &k,int temp)
{
    if(!k)return ;
    if(temp==a[k].v)
    {
        if(a[k].w>1) a[k].w--,a[k].s--;
        else if(a[k].l*a[k].r==0)
                k=a[k].l+a[k].r;
        else if(a[a[k].l].rnd<a[a[k].r].rnd)
                rturn(k),del(k,temp);
        else lturn(k),del(k,temp);
    }
    else if(temp<a[k].v) a[k].s--,del(a[k].l,temp);
    else a[k].s--,del(a[k].r,temp);
}
int ask_num(int k,int temp)
{
    if(!k)return 0;
    if(temp<=a[a[k].l].s) return ask_num(a[k].l,temp);
    else if(temp>a[a[k].l].s+a[k].w)
            return ask_num(a[k].r,temp-a[k].w-a[a[k].l].s);
    else return a[k].v;
}
int ask_rank(int k,int temp)
{
    if(!k)return 0;
    if(a[k].v==temp) return a[a[k].l].s+1;
    else if(temp>a[k].v)
            return a[a[k].l].s+a[k].w+ask_rank(a[k].r,temp);
    else return ask_rank(a[k].l,temp);
}
void ask_before(int k,int temp)
{
    if(!k) return ;
    if(temp>a[k].v)
    {
        befor=a[k].v;
        ask_before(a[k].r,temp);
    }
    else ask_before(a[k].l,temp);
}
void ask_after(int k,int temp)
{
    if(!k) return ;
    if(temp<a[k].v)
    {
        aftr=a[k].v;
        ask_after(a[k].l,temp);
    }
    else ask_after(a[k].r,temp);
}
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int tmp,c;
        scanf("%d%d",&tmp,&c);
        if(tmp==1) update(root,c);
        else if(tmp==2) del(root,c);
        else if(tmp==3) printf("%d\n",ask_rank(root,c));
        else if(tmp==4) printf("%d\n",ask_num(root,c));
        else if(tmp==5) 
        {
            befor=0;ask_before(root,c);
            printf("%d\n",befor);
        }
        else if(tmp==6) 
        {
            aftr=0;ask_after(root,c);
            printf("%d\n",aftr);
        }
    }
}

发表评论

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