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

输入

8 

1 10 

1 20 

1 30 

3 20 

4 2 

2 10 

5 25 

6 -1

输出

2 

20 

20 

20

 

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

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define LL long long#define mod#define M 1000010using 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=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) 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\n",ord(m)); else if(typ==4) printf("%lld\n",p[getnum(m)]); else printf("%lld\n",gt(m,typ-5)); } return 0;}