待補充：替罪羊樹、珂朵莉樹（TA并不是那么傳統的平衡樹）
作為碼量大、用處沒線段樹多、一考到就不會的數據結構，平衡樹這玩意 \(2023\) 年寒假學了迷迷糊糊，\(2024\) 年寒假學了還是有點迷糊（好吧沒有 \(2023\) 年迷糊了）。
學校 OJ 平衡樹的題目封禁了，看不到 \(2023\) 年寒假的提交記錄，\(2024\) 年寒假又雙叒叕重敲了一遍。
為了不再丟失代碼，在這里封存一波代碼。
題目為洛谷P3369 普通平衡樹。
（由于代碼都存在文章中，建議食用時 Ctrl+F。）

AVL

速度快常數小，功能局限性似乎較大，有點難理解，代碼稍長，幾乎沒人用。

正常版本 \(116\) 行

#include<stdio.h>
struct tree{int num,high,size,lch,rch;}s[100005];
int n,s1,s2,root,number;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void gengxin(int wheres)
{
    if(!wheres) return;
    s[wheres].high=max(s[s[wheres].lch].high,s[s[wheres].rch].high)+1;
    s[wheres].size=s[s[wheres].lch].size+1+s[s[wheres].rch].size;
}
int zig(int wheres)
{
    int tt=s[wheres].lch;
    s[wheres].lch=s[tt].rch,s[tt].rch=wheres,
    gengxin(wheres),gengxin(tt);return tt;
}
int zag(int wheres)
{
    int tt=s[wheres].rch;
    s[wheres].rch=s[tt].lch,s[tt].lch=wheres;
    gengxin(wheres),gengxin(tt);return tt;
}
int zigzag(int wheres){s[wheres].rch=zig(s[wheres].rch);return zag(wheres);}
int zagzig(int wheres){s[wheres].lch=zag(s[wheres].lch);return zig(wheres);}
void change(int &wheres)
{
    int t=0;
    if(s[s[wheres].lch].high==s[s[wheres].rch].high+2)
    {
        t=s[wheres].lch;
        if(s[s[s[wheres].lch].lch].high==s[s[wheres].rch].high+1) wheres=zig(wheres);
        else wheres=zagzig(wheres);
    }
    else if(s[s[wheres].lch].high==s[s[wheres].rch].high-2)
    {
        t=s[wheres].rch;
        if(s[s[s[wheres].rch].rch].high==s[s[wheres].lch].high+1) wheres=zag(wheres);
        else wheres=zigzag(wheres);
    }
    gengxin(t),gengxin(wheres);
}
void insert(int &wheres,int sss)
{
    if(!wheres) s[++number].num=sss,s[number].size=s[number].high=1,wheres=number;
    else if(sss<=s[wheres].num)
    {
        insert(s[wheres].lch,sss),gengxin(wheres);
        if(s[s[wheres].lch].high==s[s[wheres].rch].high+2)
        {
            if(sss<=s[s[wheres].lch].num) wheres=zig(wheres);
            else wheres=zagzig(wheres);
        }
    }
    else
    {
        insert(s[wheres].rch,sss),gengxin(wheres);
        if(s[s[wheres].rch].high==s[s[wheres].lch].high+2)
        {
            if(sss>s[s[wheres].rch].num) wheres=zag(wheres);
            else wheres=zigzag(wheres);
        }
    }
}
int deletes(int &wheres,int sss)
{
    int tmp;
    if(s[wheres].num==sss||(s[wheres].num>=sss&&(!s[wheres].lch))||(s[wheres].num<sss&&(!s[wheres].rch)))
    {
        if(s[wheres].lch==0||s[wheres].rch==0)  tmp=s[wheres].num,wheres=s[wheres].lch+s[wheres].rch;
        else tmp=s[wheres].num,s[wheres].num=deletes(s[wheres].lch,sss);
    }
    else if(s[wheres].num>=sss) tmp=deletes(s[wheres].lch,sss);
    else tmp=deletes(s[wheres].rch,sss);
    gengxin(wheres),change(wheres);return tmp;
}
int where(int wheres,int sss)
{
    if(!wheres) return 1;
    if(s[wheres].num>=sss) return where(s[wheres].lch,sss);
    return where(s[wheres].rch,sss)+1+s[s[wheres].lch].size;
}
int what(int wheres,int sss)
{
    if(s[s[wheres].lch].size>=sss) return what(s[wheres].lch,sss);
    if(s[s[wheres].lch].size+1==sss) return s[wheres].num;
    return what(s[wheres].rch,sss-1-s[s[wheres].lch].size);
}
int front(int wheres,int sss)
{
    if(!wheres) return -10000007;
    if(s[wheres].num>=sss) return front(s[wheres].lch,sss);
    int linshi=front(s[wheres].rch,sss);
    return max(s[wheres].num,linshi);
}
int back(int wheres,int sss)
{
    if(!wheres) return 10000007;
    if(s[wheres].num<=sss) return back(s[wheres].rch,sss);
    int linshi=back(s[wheres].lch,sss);
    return min(s[wheres].num,linshi);
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&s1,&s2);
        if(s1==1) insert(root,s2);
        if(s1==2) deletes(root,s2);
        if(s1==3) printf("%d\n",where(root,s2));
        if(s1==4) printf("%d\n",what(root,s2));
        if(s1==5) printf("%d\n",front(root,s2));
        if(s1==6) printf("%d\n",back(root,s2));
    }
}

壓行版本 \(94\) 行

#include<stdio.h>
int n,a,b,root,cnt;
struct sss{int deep,num,size,ch[2];}tree[100005];
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void up(int rt)
{
    if(rt)  tree[rt].deep=max(tree[tree[rt].ch[0]].deep,tree[tree[rt].ch[1]].deep)+1,
    tree[rt].size=tree[tree[rt].ch[0]].size+tree[tree[rt].ch[1]].size+1;
}
void rotate(int &rt,int wh)//zig:0 zag:1
{
    int ls=tree[rt].ch[wh];
    tree[rt].ch[wh]=tree[ls].ch[wh^1],
    tree[ls].ch[wh^1]=rt,up(rt),up(ls),rt=ls;
}
void double_rotate(int &rt,int wh){rotate(tree[rt].ch[wh],wh^1),rotate(rt,wh);}//zigzag:1 zagzig:0
void change(int &rt)
{
    int which=0;
    if(tree[tree[rt].ch[0]].deep==tree[tree[rt].ch[1]].deep+2)
    {
        which=tree[rt].ch[0];
        if(tree[tree[tree[rt].ch[0]].ch[0]].deep==tree[tree[rt].ch[1]].deep+1) rotate(rt,0);
        else double_rotate(rt,0);
    }
    else if(tree[tree[rt].ch[1]].deep==tree[tree[rt].ch[0]].deep+2)
    {
        which=tree[rt].ch[1];
        if(tree[tree[tree[rt].ch[1]].ch[1]].deep==tree[tree[rt].ch[0]].deep+1) rotate(rt,1);
        else double_rotate(rt,1);
    }
    up(which),up(rt);
}
void insert(int &rt,int ss)
{
    if(!rt) {tree[++cnt].num=ss,tree[cnt].size=tree[cnt].deep=1,rt=cnt;return;}
    bool downer=ss>tree[rt].num;
    insert(tree[rt].ch[downer],ss),up(rt);
    if(tree[tree[rt].ch[downer]].deep==tree[tree[rt].ch[downer^1]].deep+2)
    {
        if((ss<=tree[tree[rt].ch[downer]].num)^downer) rotate(rt,downer);
        else double_rotate(rt,downer);
    }
}
int deletes(int &rt,int ss)
{
    int rts;
    if(tree[rt].num==ss||(ss<=tree[rt].num&&(!tree[rt].ch[0]))||(ss>tree[rt].num&&(!tree[rt].ch[1])))
    {
        if((!tree[rt].ch[0])||(!tree[rt].ch[1])) rts=tree[rt].num,rt=tree[rt].ch[0]+tree[rt].ch[1];
        else rts=tree[rt].num,tree[rt].num=deletes(tree[rt].ch[0],ss);
    }
    else rts=deletes(tree[rt].ch[ss>tree[rt].num],ss);
    up(rt),change(rt);return rts;
}
int rank(int rt,int ss)
{
    if(!rt) return 1;
    if(ss<=tree[rt].num) return rank(tree[rt].ch[0],ss);
    return rank(tree[rt].ch[1],ss)+1+tree[tree[rt].ch[0]].size;
}
int what(int rt,int ss)
{
    if(ss<=tree[tree[rt].ch[0]].size) return what(tree[rt].ch[0],ss);
    if(ss==tree[tree[rt].ch[0]].size+1) return tree[rt].num;
    return what(tree[rt].ch[1],ss-1-tree[tree[rt].ch[0]].size);
}
int front(int rt,int ss)
{
    if(!rt) return -10000007;
    if(ss<=tree[rt].num) return front(tree[rt].ch[0],ss);
    return max(front(tree[rt].ch[1],ss),tree[rt].num);
}
int back(int rt,int ss)
{
    if(!rt) return 10000007;
    if(ss>=tree[rt].num) return back(tree[rt].ch[1],ss);
    return min(tree[rt].ch[0],tree[rt].num);
}
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&a,&b);
        if(a==1) insert(root,b);
        if(a==2) deletes(root,b);
        if(a==3) printf("%d\n",rank(root,b));
        if(a==4) printf("%d\n",what(root,b));
        if(a==5) printf("%d\n",front(root,b));
        if(a==6) printf("%d\n",back(root,b));
    }
}

旋轉 Treap

局限性未知，代碼較短小精悍，容易理解。
作為弱平衡樹，它沒有 AVL 那么嚴格，同時因為它是以堆性質為判別依據旋轉而不是以二叉搜索樹性質為判別依據旋轉的，它的旋轉方式簡單易懂。
速度不慢，但沒有 AVL 快，不過也夠用了。
一個奇怪的問題：在人品極度匱乏的情況下，隨機生成的“堆種子”會卡壞這棵 Treap。。。（不過已經很久沒見過被卡了，所以如果出現每次運行結果不同建議先別懷疑隨機種子出鍋……）

正常版本 \(89\) 行

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
struct tree{int ch[2],num,better,size;}s[100005];
int n,s1,s2,root,number,i;
void gengxin(int sss){if(sss) s[sss].size=1+s[s[sss].ch[0]].size+s[s[sss].ch[1]].size;}
void xuanzhuan(int &wheres,int whats)
{
    int linshi=s[wheres].ch[whats];
    s[wheres].ch[whats]=s[linshi].ch[whats^1];
    s[linshi].ch[1^whats]=wheres;
    gengxin(wheres),gengxin(linshi);
    wheres=linshi;
}
void insert(int &wheres,int sss)
{
    if(!wheres) s[++number].num=sss,s[number].better=rand(),s[number].size=1+s[s[number].ch[0]].size+s[s[number].ch[1]].size,wheres=number;
    else if(sss<=s[wheres].num)
    {
        insert(s[wheres].ch[0],sss);
        if(s[wheres].ch[0]&&s[wheres].better>s[s[wheres].ch[0]].better) xuanzhuan(wheres,0);
        gengxin(wheres);
    }
    else
    {
        insert(s[wheres].ch[1],sss);
        if(s[wheres].ch[1]&&s[wheres].better>s[s[wheres].ch[1]].better) xuanzhuan(wheres,1);
        gengxin(wheres);
    }
}
int deletes(int &wheres,int sss)
{
    int tmp;
    if(s[wheres].num==sss||s[wheres].num<sss&&(!s[wheres].ch[1])||s[wheres].num>sss&&(!s[wheres].ch[0]))
    {
        if((!s[wheres].ch[0])||(!s[wheres].ch[1])) tmp=s[wheres].num,wheres=s[wheres].ch[0]+s[wheres].ch[1];
        else tmp=s[wheres].num,s[wheres].num=deletes(s[wheres].ch[0],sss);
    }
    else if(s[wheres].num<sss) tmp=deletes(s[wheres].ch[1],sss);
    else tmp=deletes(s[wheres].ch[0],sss);
    gengxin(wheres);
    return tmp;
}
int where(int wheres,int sss)
{
    if(!wheres) return 1;
    if(sss>s[wheres].num) return s[s[wheres].ch[0]].size+1+where(s[wheres].ch[1],sss);
    else return where(s[wheres].ch[0],sss);
}
int what(int wheres,int sss)
{
    if(s[s[wheres].ch[0]].size>=sss) return what(s[wheres].ch[0],sss);
    else if(s[s[wheres].ch[0]].size+1==sss) return s[wheres].num;
    else return what(s[wheres].ch[1],sss-1-s[s[wheres].ch[0]].size);
}
int front(int wheres,int sss)
{
    if(!wheres) return -10000007;
    else if(s[wheres].num>=sss) return front(s[wheres].ch[0],sss);
    else
    {
        int linshi=front(s[wheres].ch[1],sss);
        return (s[wheres].num>linshi)?s[wheres].num:linshi;
    }
}
int back(int wheres,int sss)
{
    if(!wheres) return 10000007;
    else if(s[wheres].num<=sss) return back(s[wheres].ch[1],sss);
    else
    {
        int linshi=back(s[wheres].ch[0],sss);
        return (s[wheres].num<linshi)?s[wheres].num:linshi;
    }
}
int main()
{
    srand(time(0)),scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%d%d",&s1,&s2);
        if(s1==1) insert(root,s2);
        if(s1==2) deletes(root,s2);
        if(s1==3) printf("%d\n",where(root,s2));
        if(s1==4) printf("%d\n",what(root,s2));
        if(s1==5) printf("%d\n",front(root,s2));
        if(s1==6) printf("%d\n",back(root,s2));
    }
}

壓行版本 \(72\) 行

#include<time.h>
#include<stdio.h>
#include<stdlib.h>
int n,a,b,root,num;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
struct sss{int ch[2],num,better,size;}tree[100005];
void up(int rt){if(rt) tree[rt].size=tree[tree[rt].ch[0]].size+tree[tree[rt].ch[1]].size+1;}
void rotate(int &rt,int wh)
{
    int ls=tree[rt].ch[wh];
    tree[rt].ch[wh]=tree[ls].ch[wh^1],
    tree[ls].ch[wh^1]=rt;
    up(rt),up(ls),rt=ls;
}
void insert(int &rt,int ss)
{
    if(!rt) {tree[rt=++num].num=ss,tree[rt].size=1,tree[rt].better=rand();return;}
    bool downer=ss>tree[rt].num;
    insert(tree[rt].ch[downer],ss);
    if(tree[rt].ch[downer]&&tree[rt].better>tree[tree[rt].ch[downer]].better) rotate(rt,downer);
    up(rt);
}
int deletes(int &rt,int ss)
{
    int rts=0;
    if(tree[rt].num==ss||ss<tree[rt].num&&(!tree[rt].ch[0])||(ss>tree[rt].num&&(!tree[rt].ch[1])))
    {
        if(!tree[rt].ch[0]||!tree[rt].ch[1]) rts=tree[rt].num,rt=tree[rt].ch[0]+tree[rt].ch[1];
        else rts=tree[rt].num,tree[rt].num=deletes(tree[rt].ch[0],ss);
    }
    else rts=deletes(tree[rt].ch[(ss>tree[rt].num)],ss);
    up(rt);return rts;
}
int rank(int rt,int ss)
{
    if(!rt) return 1;
    if(ss<=tree[rt].num) return rank(tree[rt].ch[0],ss);
    return rank(tree[rt].ch[1],ss)+1+tree[tree[rt].ch[0]].size;
}
int what(int rt,int ss)
{
    if(ss<=tree[tree[rt].ch[0]].size) return what(tree[rt].ch[0],ss);
    if(ss==tree[tree[rt].ch[0]].size+1) return tree[rt].num;
    return what(tree[rt].ch[1],ss-1-tree[tree[rt].ch[0]].size);
}
int front(int rt,int ss)
{
    if(!rt) return -10000007;
    if(ss<=tree[rt].num) return front(tree[rt].ch[0],ss);
    return max(front(tree[rt].ch[1],ss),tree[rt].num);
}
int back(int rt,int ss)
{
    if(!rt) return 10000007;
    if(ss>=tree[rt].num) return back(tree[rt].ch[1],ss);
    return min(back(tree[rt].ch[0],ss),tree[rt].num);
}
int main()
{
    srand(time(0)),scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&a,&b);
        if(a==1) insert(root,b);
        if(a==2) deletes(root,b);
        if(a==3) printf("%d\n",rank(root,b));
        if(a==4) printf("%d\n",what(root,b));
        if(a==5) printf("%d\n",front(root,b));
        if(a==6) printf("%d\n",back(root,b));
    }
}

FHQ Treap（非旋Treap）

作為我們最喜歡的平衡樹之一，摒棄了旋轉操作的 FHQ Treap 使用分裂和合并操作，令平衡樹顯得更加自然。
速度和旋轉 Treap 一樣不算慢（盡管不是最快的），代碼簡短易于理解，在我的極致壓縮下更是達到了 \(72\) 行。。。
但我最喜歡它的一點是它可以處理區間翻轉等類似問題，這樣我就不用去打惡心的 Splay 了。（據說除了 LCT 以外 Splay 能做的 FHQ Treap 都能做？）
另：因為它的基本性質，和，咳，普通 Treap 是一樣的，所以和普通 Treap 一樣，如果 RP 太少，那么可能會被卡掉。。。（不過已經很久沒見過被卡了，所以如果出現每次運行結果不同建議先別懷疑隨機種子出鍋……）

代碼 \(72\) 行

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
struct tree{int num,size,better,ch[2];}s[100005];
int n,s1,s2,root,root1,root2,number,ans;
void gengxin(int wheres){if(wheres) s[wheres].size=s[s[wheres].ch[0]].size+1+s[s[wheres].ch[1]].size;}
void split(int wheres,int &x,int &y,int sss)
{
    if(!wheres) x=y=0;
    else if(s[wheres].num>sss) y=wheres,split(s[wheres].ch[0],x,s[y].ch[0],sss);
    else x=wheres,split(s[wheres].ch[1],s[x].ch[1],y,sss);
    gengxin(wheres);
}
void merge(int &wheres,int x,int y)
{
    if((!x)||(!y)) wheres=x+y;
    else if(s[x].better<s[y].better) wheres=x,merge(s[wheres].ch[1],s[wheres].ch[1],y);
    else wheres=y,merge(s[wheres].ch[0],x,s[wheres].ch[0]);
    gengxin(wheres);
}
void insert(int &wheres,int sss)
{
    split(root,root1,root2,sss);
    s[++number].num=sss,s[number].better=rand(),s[number].size=1,wheres=number;
    merge(root1,root1,number),merge(wheres,root1,root2);
}
void deletes(int &wheres,int sss)
{
    int zzz;
    split(wheres,root1,root2,sss),split(root1,root1,zzz,sss-1);
    merge(zzz,s[zzz].ch[0],s[zzz].ch[1]),merge(wheres,root1,zzz),merge(wheres,wheres,root2);
}
inline int where(int wheres,int sss)
{
    if(!wheres) return 1;
    if(sss>s[wheres].num) return s[s[wheres].ch[0]].size+1+where(s[wheres].ch[1],sss);
    else return where(s[wheres].ch[0],sss);
}
inline int what(int wheres,int sss)
{
    if(s[s[wheres].ch[0]].size>=sss) return what(s[wheres].ch[0],sss);
    else if(s[s[wheres].ch[0]].size+1==sss) return s[wheres].num;
    else return what(s[wheres].ch[1],sss-1-s[s[wheres].ch[0]].size);
}
int front(int wheres,int sss)
{
    if(!wheres) return -10000007;
    if(s[wheres].num>=sss) return front(s[wheres].ch[0],sss);
    int linshi=front(s[wheres].ch[1],sss);
    return (s[wheres].num>linshi)?s[wheres].num:linshi;
}
int back(int wheres,int sss)
{
    if(!wheres) return 10000007;
    if(s[wheres].num<=sss) return back(s[wheres].ch[1],sss);
    int linshi=back(s[wheres].ch[0],sss);
    return (s[wheres].num<linshi)?s[wheres].num:linshi;
}
int main()
{
    srand(time(0)),scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&s1,&s2);
        if(s1==1) insert(root,s2);
        if(s1==2) deletes(root,s2);
        if(s1==3) printf("%d\n",where(root,s2));
        if(s1==4) printf("%d\n",what(root,s2));
        if(s1==5) printf("%d\n",front(root,s2));
        if(s1==6) printf("%d\n",back(root,s2));
    }
}

Splay

作為本人最討厭的平衡樹，速度本人實測是最慢的（在學校 OJ 過了的在洛谷甚至沒 A，T 了最后一個點），代碼是我在學校 OJ 唯一沒找到的，長度實現下來是最長的，雖然旋轉操作其實也不那么難理解，但代碼是我調了最久的。最令人難受的是為什么沒人寫遞歸版本啊！
但是它似乎是全部平衡樹中功能最多的，除了能區間翻轉，還能 LCT。所以我非學不可。

代碼 \(120\) 行

#include<stdio.h>
int n,a,b,root,cnt,ans;
struct node{int ch[2],num,size,fa,samer;}tree[1000005];
void clear(int rt){tree[rt]=tree[1000004];}
bool soner(int rt){return tree[tree[rt].fa].ch[1]==rt;}
void up(int rt)
{
    if(rt)
    {
        tree[rt].size=tree[rt].samer;
        if(tree[rt].ch[0]) tree[rt].size+=tree[tree[rt].ch[0]].size;
        if(tree[rt].ch[1]) tree[rt].size+=tree[tree[rt].ch[1]].size;
    }
}
void rotate(int rt)
{
    int fa=tree[rt].fa,gfa=tree[fa].fa,sonrt=soner(rt);
    tree[fa].ch[sonrt]=tree[rt].ch[!sonrt],
    tree[tree[fa].ch[sonrt]].fa=fa,
    tree[rt].ch[!sonrt]=fa,
    tree[fa].fa=rt,tree[rt].fa=gfa;
    if(gfa) tree[gfa].ch[tree[gfa].ch[1]==fa]=rt;
    up(fa),up(rt);
}
void splay(int rt)
{
    for(int fa;fa=tree[rt].fa;rotate(rt)) if(tree[fa].fa) rotate((soner(fa)==soner(rt))?fa:rt);
    root=rt;
}
void insert(int num)
{
    if(!root){root=++cnt,tree[cnt].samer++,tree[cnt].num=num,up(root);return;}
    int rt=root,fa=0;
    while(1)
    {
        if(num==tree[rt].num){tree[rt].samer++,up(rt),up(fa),splay(rt);break;}
        fa=rt,rt=tree[rt].ch[tree[rt].num<num];
        if(!rt)
        {
            cnt++,tree[cnt].fa=fa,tree[cnt].samer++,
            tree[fa].ch[tree[fa].num<num]=cnt,tree[cnt].num=num,
            up(rt),up(fa),splay(cnt);break;
        }
    }
}
void find(int num)
{
    int rt=root;
    while(1)
    {
        if(tree[rt].num==num) {splay(rt);return;}
        rt=tree[rt].ch[num>tree[rt].num];
    }
}
int front(int num)
{
    int rt=root;
    rt=tree[rt].ch[0];
    if(!rt) return -10000007;
    while(tree[rt].ch[1]) rt=tree[rt].ch[1];
    return rt; 
}
int back(int num)
{
    int rt=root;
    rt=tree[rt].ch[1];
    if(!rt) return 10000007;
    while(tree[rt].ch[0]) rt=tree[rt].ch[0];
    return rt; 
}
void deletes(int num)
{
    find(num);
    int ls=tree[root].ch[0],rs=tree[root].ch[1];
    if(tree[root].samer>1) tree[root].samer--,up(root);
    else if(ls&&rs)
    {
        int nums=front(num);
        clear(root),root=ls,tree[ls].fa=tree[rs].fa=0,
        splay(nums),tree[root].ch[1]=rs,tree[rs].fa=root,up(root);
    }
    else if(ls) clear(root),tree[ls].fa=0,root=ls;
    else if(rs) clear(root),tree[rs].fa=0,root=rs;
    else clear(root),cnt=root=0;
}
int rank(int num)
{
    insert(num);
    int rts=tree[tree[root].ch[0]].size+1;
    deletes(num);return rts;
}
int what(int num)
{
    int rt=root;
    while(1)
    {
        if(tree[rt].ch[0]&&num<=tree[tree[rt].ch[0]].size) rt=tree[rt].ch[0];
        else
        {
            num-=tree[tree[rt].ch[0]].size;
            if(num<=tree[rt].samer) {splay(rt);return tree[rt].num;}
            num-=tree[rt].samer,rt=tree[rt].ch[1];
        }
    }
    return tree[rt].num;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) 
    {
        scanf("%d%d",&a,&b);
        if(a==1) insert(b);
        if(a==2) deletes(b);
        if(a==3) printf("%d\n",rank(b));
        if(a==4) printf("%d\n",what(b));
        if(a==5) {insert(b),printf("%d\n",tree[front(b)].num),deletes(b);}
        if(a==6) {insert(b),printf("%d\n",tree[back(b)].num),deletes(b);}
    }
}