TYVJ P1728 普通平衡树

P1728 普通平衡树

时间: 1000ms / 空间: 131072KiB / Java类名: Main

背景

此为平衡树系列第一道：普通平衡树

描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
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每行输出一个数，表示对应答案

测试样例1

输入

1 10
1 20
1 30
3 20
4 2
2 10
5 25
6 -1

输出

2
20
20
20

splay裸体，无聊随便打一打,多练练手吧。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define mod
#define M 1000010
using namespace std;
LL read(){
    LL nm=0,oe=1;char cw=getchar();
    while(!isdigit(cw)) oe=cw=='-'?-oe:oe,cw=getchar();
    while(isdigit(cw)) nm=nm*10+(cw-'0'),cw=getchar();
    return nm*oe;
}
LL n,m,l[M],r[M],sz[M],tp[M],p[M],num[M],cnt,T,ace,typ;
inline void pushup(LL x){sz[x]=sz[l[x]]+sz[r[x]]+num[x];}
void rotate(LL x){
    if(x==ace) return;
    LL top=tp[x];sz[x]=sz[top];
    if(l[top]==x) sz[top]=sz[r[top]]+sz[r[x]]+num[top];
    else sz[top]=sz[l[top]]+sz[l[x]]+num[top];
    if(top==ace){ace=x,tp[top]=ace;}
    else{
        tp[x]=tp[top];
        if(l[tp[top]]==top) l[tp[top]]=x,tp[top]=x;
        else r[tp[top]]=x,tp[top]=x;
    }
    if(l[top]==x) l[top]=r[x],tp[r[x]]=top,r[x]=top;
    else r[top]=l[x],tp[l[x]]=top,l[x]=top;
}
void splay(LL x){
    while(ace!=x){
        LL top=tp[x];
        if(top==ace) rotate(x);
        else if(l[l[tp[top]]]==x||r[r[tp[top]]]==x) rotate(top);
        else rotate(x);
    }
}
void insert(LL x){
    if(ace==0){ace=++cnt,p[ace]=x,sz[ace]=num[ace]=1;return;}
    LL k=ace,last=0,sta=0,CNT=0;
    while(true){
        if(k==0){
            p[++cnt]=x,tp[cnt]=last,sz[cnt]=num[cnt]=1;
            if(sta==1) r[last]=cnt;
            else l[last]=cnt;
            break;
        }
        last=k;
        if(p[k]<x) k=r[k],sta=1;
        else if(p[k]>x) k=l[k],sta=2;
        else{num[k]++;break;}
    }
    while(true){
        sz[last]++,CNT++;
        if(last==ace) break;
        last=tp[last];
    }
    splay(cnt);
}
LL find(LL x){
    LL k=ace,CT=0;
      while(p[k]!=x&&k>0){
        if(p[k]>x) k=l[k];
        else k=r[k];
        CT++;
    }
    if(CT>=50&&k>0) splay(k);
    return k;
}
LL gt(LL x,LL tpe){
    LL k=find(x),rt1=-100000012,rt2=100000012;
    if(k==0){
        for(LL t=ace;t>0;){
            if(p[t]>x) rt2=min(rt2,p[t]),t=l[t];
            else rt1=max(rt1,p[t]),t=r[t];
        }
        return tpe==0?rt1:rt2;
    }
    splay(k);
    for(LL t=l[k];t!=0;t=r[t]) rt1=max(rt1,p[t]);
    for(LL t=r[k];t!=0;t=l[t]) rt2=min(rt2,p[t]);
    return tpe==0?rt1:rt2;
}
LL ord(LL x){
    LL k=find(x);
    splay(k);
    return sz[l[k]]+1;
}
LL getnum(LL x){
    LL k=ace,od=x;
    while(sz[l[k]]+1>od||sz[l[k]]+num[k]<od){
        if(sz[l[k]]+1>od) k=l[k];
        else od-=sz[k]-sz[r[k]],k=r[k];
    }
    return k;
}
void del(LL x){
    LL pos=find(x),last=0;
    if(num[pos]>1){
       num[pos]--,last=pos;
        while(true){
            sz[last]--;
            if(last==ace) break;
            last=tp[last];
        }
        return;
    }
    splay(pos),sz[pos]--;
    if(l[pos]==0&&r[pos]==0){ace=0;return;}
    else if(l[pos]==0) ace=r[pos];
    else if(r[pos]==0) ace=l[pos];
    else{
        LL ss=l[pos];
        if(r[ss]==0){
            p[pos]=p[ss],num[pos]=num[ss];
            tp[l[ss]]=tp[ss],l[tp[ss]]=l[ss];
            return;
        }
        while(r[ss]>0) ss=r[ss];
        p[pos]=p[ss],num[pos]=num[ss];
        tp[l[ss]]=tp[ss],r[tp[ss]]=l[ss];
        for(LL i=l[ss];i!=ace;i=tp[i]) pushup(tp[i]);
    }
}
int main(){
    T=read();
    while(T--){
        typ=read(),m=read(),num[0]=find(m);
        if(typ==1) insert(m);
        else if(typ==2) del(m);
        else if(typ==3) printf("%lld
",ord(m));
        else if(typ==4) printf("%lld
",p[getnum(m)]);
        else printf("%lld
",gt(m,typ-5));
    }
    return 0;
}