WBLT 学习笔记 & 复杂度完整证明

LEWISAK · 2026-03-19 16:55:18 · 算法·理论

Latex 很多，加载久很正常。

可持久化咕一会，本篇只介绍朴素 WBLT 相关内容。

1 算法过程

由于该算法证明比较困难，所以这一部分先将其搁置介绍实现。

WBLT，顾名思义，就是 Weight Balanced Leafy Tree。

Leafy Tree：

1. 所有信息维护在叶子上，其他节点只负责合并信息、维护平衡等。
2. 非叶子节点必有两个儿子。

注意到实际上线段树就是一种 Leafy Tree。

接下来以普通平衡树为例。

1.1 节点信息

需要维护 ch[x][2] 表示左右儿子，siz[x] 表示子树中叶子节点的个数，val[x] 表示子树 中的最大键值

struct{
    int val,siz,ch[2];
}tr[200200];
#define ch(p,x) tr[x].ch[p]
#define val(x) tr[x].val
#define sz(x) tr[x].siz

1.2 辅助函数

一些非常好实现的辅助函数：

• up(x)：合并 x 的左右儿子信息。
• nw(v)：新建一个权值为 v 的点。
• del(x)：删除 x。
• join(x,y)：新建一个节点 z 使其左右儿子为 x 和 y 并返回 z。
• cut(x)：删除 x，返回它的左右儿子。

void up(int x){
    sz(x)=sz(ch(0,x))+sz(ch(1,x));
    val(x)=val(ch(1,x));
}
int nw(int v=0){//v=0 时是非叶子节点
    int x=top?st[top--]:++cnt;//回收站有点就拿出来用
    sz(x)=ch(0,x)=ch(1,x)=0;
    val(x)=v;
    sz(x)=1;//情理上 v=0 时这个 siz 要赋为 0，但反正要 up 所以不影响
    return x;
}
void del(int &x){
    st[++top]=x;//经典回收站，省空间复杂度
    x=0;
}
int join(int x,int y){
    int z=nw();
    ch(0,z)=x;
    ch(1,z)=y;
    up(z);
    return z;
}
pair<int,int> cut(int &x){
    int l=ch(0,x),r=ch(1,x);
    del(x);
    return {l,r};
}

1.3 平衡

WBLT 的核心。

对于一个节点 x，我们定义其平衡度 \rho 为：

对于一棵树 T 而言，其平衡度定义为 \min\limits_{x\in T} \rho_x。

不妨假设我们能够通过一些方法使树保持平衡度 =\alpha(0<\alpha\le \frac{1}{2})，那么此时每向子节点移动一次，siz 就至少会缩减到原来的 \frac{1}{1-\alpha} 倍，于是树高为 \log_{\frac{1}{1-\alpha}} n=\log_2 n\times \log_\frac{1}{1-\alpha} 2。

当你想控制 \log_{\frac{1}{1-\alpha}}2 这个常数在 3 以下时，大概需要保证 \alpha>\frac{1}{5}，阅读 2~4 章节后，你会发现我们的 \alpha 必然会满足该限制。

1.3.1 维护方式

主流的维护方式有旋转维护和分裂合并维护两种，由于我比较懒，这里只介绍旋转维护。

WBLT 的旋转方式和 Splay，Treap 等平衡树的完全一样。

这里令 y 过轻，即 y<\alpha(x+y)。

接下来介绍如何选择这两种旋转方式进行维护平衡：

发现进行一次单旋操作后，相当于将 w 移动到了右子树中，所以当 w 过重时，我们应该改用双旋，于是我们指定了以下方案（有常数 \beta）：

• 当 w\le \beta x 时，单旋。
• 当 w>\beta x 时，双旋。

这里取 \beta=\frac{1}{2-\alpha}，对正确性感到疑惑的去看第 2 节。

const double alpha=0.292;
void rotate(int &x,bool fl){//单旋
    int a,b,c,d;
    tie(a,b)=cut(x);
    if(fl){
        tie(c,d)=cut(b);
        x=join(join(a,c),d);
    }
    else{
        tie(c,d)=cut(a);
        x=join(c,join(d,b));
    }
}
bool heavy(int x,int y){//是否超重
    return y<alpha*(x+y);
}
bool nedtwo(int x,bool fl){//是否需要双旋
    return sz(ch(fl,x))>sz(x)/(2-alpha);
}
void balance(int &x){
    if(sz(x)==1) return;
    bool fl=sz(ch(1,x))>sz(ch(0,x));//fl 为较重的儿子
    if(!heavy(sz(ch(fl,x)),sz(ch(!fl,x)))) return;
    if(nedtwo(ch(fl,x),!fl)){
        rotate(ch(fl,x),!fl);
    }
    rotate(x,fl);
}

1.4 插入 & 删除

这里插入了一个值为 4 的元素，我们要找到它的前驱/后继，然后新建一个节点，让它成为这两个节点的父亲并根据大小决定谁是左儿子。

对于删除，需要删除节点后让异侧的儿子替换父亲的位置以保证 Leafy。

void insert(int &x,int v){
    if(!x){//空节点直接用 v 替换
        x=nw(v);
        return;
    }
    if(sz(x)==1){
        bool fl=v>=val(x);//决定 v 是左儿子还是右儿子
        ch(fl,x)=nw(v);
        ch(!fl,x)=nw(val(x));
        up(x);
        return;
    }
    bool fl=v>val(ch(0,x));//v 在左边还是右边
    insert(ch(fl,x),v);
    up(x);
    balance(x);
}
void remove(int &x,int v){
    if(!x) return;//查无此人不用删了
    if(sz(x)==1){
        if(val(x)==v) del(x);//找到 v 并删除
        return;
    }
    bool fl=v>val(ch(0,x));//v 在左边还是右边
    remove(ch(fl,x),v);
    if(!ch(fl,x)){
        x=ch(!fl,x);//让异侧的儿子替换父亲
        return;
    }
    up(x);
    balance(x);
}

1.5 查询排名

类似线段树上二分，v 左边数的个数就是答案。

int rk(int x,int v){
    if(!x) return 0;
    int ans=0;
    while(sz(x)>1){
        if(val(ch(0,x))<v){//左边的最大值比 v 小，去右子树
            ans+=sz(ch(0,x));//累加答案
            x=ch(1,x);
        }
        else{//去左子树
            x=ch(0,x);
        }
    }
    return ans+(val(x)<v?1:0);//叶子的贡献要单独计算
}

1.6 查询第 k 名

还是类似线段树二分，没啥说的🤐。

int kth(int x,int k){
    while(sz(x)>1){
        if(sz(ch(0,x))>=k){//第 k 名在左边
            x=ch(0,x);
        }
        else{
            k-=sz(ch(0,x));
            x=ch(1,x);
        }
    }
    return val(x);
}

1.7 查询前驱 & 后继

可以取巧地用 1.5 和 1.6 搓出来🤔。

int pre(int v){
    return kth(rk(v)-1);
}
int nxt(int v){
    return kth(rk(v+1));
}

1.8 合并

为保证合并后平衡，我们需要将过重的一方拆开和另一方递归合并，当然不过重直接合并就可以了。

对正确性/复杂度疑惑的去看第 3 节。

int merge(int x,int y){
    if(!x||!y) return x+y;
    int a,b;
    if(heavy(sz(x),sz(y))){//x 过重
        tie(a,b)=cut(x);
        int z=join(a,merge(b,y));//给 y 分一个接着递归
        balance(z);
        return z;
    }
    else if(heavy(sz(y),sz(x))){
        tie(a,b)=cut(y);
        int z=join(merge(x,a),b);
        balance(z);
        return z;
    }
    else{//直接合并
        return join(x,y);
    }
}

1.9 分裂

这里以分裂出一个大小为 k 的子树为例。

注意这里的复杂度是单 log 的，证明在第 4 节。

pair<int,int> split(int x,int k){
    if(!x) return {0,0};
    if(!k) return {0,x};
    if(k==sz(x)) return {x,0};//大小恰好
    int a,b,c,d;
    tie(a,b)=cut(x);
    if(k<=sz(a)){//左儿子需要被分裂
        tie(c,d)=split(a,k);
        return {c,merge(d,b)};
    }
    else{//左儿子整个在左边
        tie(c,d)=split(b,k-sz(a));
        return {merge(a,c),d};
    }
}

2 旋转相关证明

或将成为最易理解的证明？

我保证我奶奶都能看懂，如果你看不懂，说明你不是我奶奶。

长文证明难免纰漏，发现问题欢迎指出。

虽然 OI-wiki 证明的不完整有的地方还有问题，但是作为我查到的为数不多复杂度证明已经是几乎最完善的一篇了，侧面反映了此类资料的不足。

2.1 引理-旋转后平衡度的变化规律

OI-wiki 将这一部分跳过了😅。

下文用 \gamma _a 表示 a 旋转后的平衡度。

2.1.1 单旋

由定义有：

2.1.2 双旋

由定义有：

2.2 旋转后平衡证明

这里 \beta 直接带入了 \frac{1}{2-\alpha}，因为 \alpha 和 \beta 都不代的话你的合法范围会非常丑陋难以证明🤮：

2.2.1 取值范围隐藏条件

还是这个图：

显然失衡只会因为某一次插入/删除元素引起，这里进行分类讨论：

• 因插入引起，那么有 \frac{u}{y-1+u}\ge \alpha：

  \begin{align*} &\because\rho_x=\frac{u}{y+u}\newline &\therefore y\rho_x+u\rho_x=u\newline &\therefore y=\frac{u-u\rho_x}{\rho_x}=\frac{u}{\rho_x}-u\newline &\because \alpha\le\frac{u}{y-1+u}\newline &\therefore\alpha\le\frac{u}{\frac{u}{\rho_x}-u-1+u}=\frac{u}{\frac{u}{\rho_x}-1}=\frac{u\rho_x}{u-\rho_x}\newline &\therefore\alpha u-\alpha\rho_x\le u\rho_x\newline &\therefore u\rho_x+\alpha\rho_x\ge\alpha u\newline &\therefore \rho_x\ge\frac{\alpha u}{u+\alpha}=\frac{\alpha}{1+\frac{\alpha}{u}} \end{align*}

  由于 u 为正整数，所以 \frac{\alpha}{1+\alpha} \le \rho_x。

• 因删除引起，那么有 \frac{u+1}{y+u+1}\ge\alpha：

  \begin{align*} &\text{(省去重复部分)}\newline &\therefore y=\frac{u}{\rho_x}-u\newline &\because \alpha\le\frac{u+1}{y+u+1}=\frac{u+1}{\frac{u}{\rho_x}-u+u+1}=\frac{u+1}{\frac{u}{\rho_x}+1}=\frac{u\rho_x+\rho_x}{u+\rho_x}\newline &\therefore u\alpha+\alpha\rho_x\le u\rho_x+\rho_x\newline &\therefore u\rho_x+\rho_x-\alpha\rho_x\ge u\alpha\newline &\therefore \rho_x\ge \frac{\alpha u}{u+1-\alpha}=\frac{\alpha}{1+\frac{1-\alpha}{u}} \end{align*}

  由于 u 为正整数，所以 \frac{\alpha}{2+\alpha}\le \rho_x。

因为 0<\alpha<\frac{1}{2}，所以有： 2-\alpha > 1+\alpha\Rightarrow \frac{\alpha}{2-\alpha} < \frac{\alpha}{1+\alpha}。

综上 \frac{\alpha}{2+\alpha}\le \rho_x。

除此外有一些因 \rho_x 过小、\rho_y 平衡得出的条件：

由于一些原因，下面将删除元素且 u=1 的情况分开讨论。

人话：直接搞精度太低证不出来。

• 删除元素且 u=1：

  \begin{align*} \frac{\alpha}{2-\alpha}&\le\rho_x\newline \frac{\alpha}{2-\alpha}&\le\frac{u}{u+y}\newline \frac{\alpha}{2-\alpha}&\le\frac{1}{1+y}\newline \alpha+\alpha y&\le2-\alpha\newline y&\le\frac{2-2\alpha}{\alpha}=\frac{2}{\alpha}-2\newline \end{align*}

  由于此时 \rho_y\le\beta，所以 v_{max}=\beta y。

  观察树发现 \gamma_x 有另一种表示方式为 \frac{u}{u+v} 即 \frac{1}{1+v}，该式最小值显然在 v 取 \max 时取到，于是我们转换求证：

  \begin{align*} \gamma_x=\frac{1}{1+v}&\ge \alpha\newline \Rightarrow \frac{1}{1+\beta y}&\ge\alpha\newline {1+\beta y}&\le\frac{1}{\alpha}\newline y&\le\frac{\frac{1}{\alpha}-1}{\beta}\newline y&<\frac{\frac{1}{\alpha}}{\beta}\newline y&<\frac{1}{\alpha\beta}\newline y&<\frac{1}{\frac{\alpha}{2-\alpha}}\newline y&<\frac{2-\alpha}{\alpha}\newline y&<\frac{2}{\alpha}-1\newline \end{align*}

  而上文证过 y\le\frac{2}{\alpha}-2，所以这个部分恒成立，没有对 \alpha 的限制。

• 这时我们对于删除元素时的 $\rho_x$ 下限可以更紧一些，此时有 $u\ge 2$。 在 2.2.1 确乎证了个东西叫 $\rho_x\ge \frac{\alpha u}{u+1-\alpha}$，即 $\rho_x\ge\frac{\alpha}{1+\frac{1-\alpha}{u}}$，右式的最小值显然在 $u$ 取 $\min=2$ 时取得，所以此时有 $\rho_x\ge\frac{2\alpha}{3-\alpha}$，和插入元素的限制 $\frac{\alpha}{1+\alpha}$ 取 $\min$ 后限制仍为 $\rho_x\ge\frac{2\alpha}{3-\alpha}$。 回到求证，$\gamma_x=\frac{\rho_x}{\rho_x+\rho_y(1-\rho_x)}$，这个的最小值显然在 $\rho_x$ 取最小，$\rho_y$ 取最大时取得。 $$ \gamma_x\ge\frac{\frac{2\alpha}{3-\alpha}}{\frac{2\alpha}{3-\alpha}+\frac{1}{2-\alpha}(1-\frac{2\alpha}{3-\alpha})}\ge\alpha $$ 这一坨在 $0<\alpha<1$ 时等价于 $\alpha(\alpha-\frac{1}{2})(\alpha-1)\ge 0$，所以这个部分对 $\alpha$ 的限制为 $0\le \alpha \le \frac{1}{2}$，咋比定义弱🤨。

\gamma_x\le1-\alpha

这个倒是可以直接搞，显然 \gamma_x=\frac{\rho_x}{\rho_x+\rho_y(1-\rho_x)} 在 \rho_x 取最大， \rho_y 取最小时有最大值。

这在 0<\alpha<1 时等价于 \alpha^{2}-3\alpha+1\ge0，对 \alpha 的限制为 \alpha \le \frac{3-\sqrt{5}}{2}。

\alpha\le\gamma_y\le1-\alpha

这全都能直接搞，舒服了，显然 \gamma_y=\rho_x+\rho_y(1-\rho_x) 在 \rho_x,\rho_y 取最大时有最大值，在 \rho_x,\rho_y 取最小时有最小值。

这坨算出来对 \alpha 的限制为 \alpha\le1-\frac{\sqrt2}{2}。

2.2.3 双旋

即 \rho_y>\frac{1}{2-\alpha}。

整理已知：

整理求证：

\alpha\le\gamma_x

和单旋类似的，这里的证明需要一些手法🤏。

把 \rho_y,\rho_u 最大值带入：

可以把式子化为：

对于插入的情况，由于 \rho_x\ge\frac{\alpha}{1+\alpha}，故此时显然成立，否则利用 2.2.1 证过的 \rho_x\ge \frac{\alpha u}{u+1-\alpha} 分类讨论：

• $$ \rho_x\ge\frac{3\alpha}{4-\alpha}\ge\frac{\alpha(1-\alpha)}{1+\alpha(1-\alpha)} $$ 上式得出的限制为 $\alpha\ge\frac{2-\sqrt{3}}{2}$。
• $$ \begin{align*} \frac{\alpha u}{u+1-\alpha}&\le\rho_x\newline \frac{\alpha u}{u+1-\alpha}&\le\frac{u}{u+y}\newline \frac{2 \alpha}{2+1-\alpha}&\le\frac{2}{2+y}\newline 4\alpha+2y\alpha&\le6-2\alpha\newline y&\le\frac{3-3\alpha}{\alpha}=\frac{3}{\alpha}-3\newline y&\le\left\lfloor\frac{3}{a}\right\rfloor-3 \end{align*} $$ 又因为 $b\le \left\lfloor(1-\alpha)\left\lfloor(1-\alpha)y\right\rfloor\right\rfloor$（往下一层权值乘 $1-\alpha$），那么转化求证： $$ \begin{align*} \gamma_x=\frac{u}{u+b}&\ge\alpha\newline \frac{2}{2+\left\lfloor(1-\alpha)\left\lfloor(1-\alpha)\left\lfloor\frac{3}{a}\right\rfloor-3\right\rfloor\right\rfloor}&\ge\alpha \end{align*} $$ 或许是因为能力太弱，我实在不认为这是人类能解的东西，事实上，左式在 $0<\alpha<1$ 时的函数图像如图：  至于该不等式的解，我~~尝试后~~发现为 $\alpha>\frac{3}{22}$，实际上解集不止这些，但是与 $\alpha\ge\frac{2-\sqrt{3}}{2}$ 求交后能筛掉其他部分，如图：  如果有数学领域大手子能严谨解出这个不等式可以跟我说下解法，不胜感激🖐😭🖐。
• $$ \begin{align*} \frac{\alpha u}{u+1-\alpha}&\le\rho_x\newline \frac{\alpha u}{u+1-\alpha}&\le\frac{u}{u+y}\newline \frac{\alpha}{2-\alpha}&\le\frac{1}{1+y}\newline \alpha+y\alpha&\le2-\alpha\newline y&\le\frac{2-2\alpha}{\alpha}=\frac{2}{\alpha}-2\newline y&\le\left\lfloor\frac{2}{a}\right\rfloor-2 \end{align*} $$ 又因为 $b\le \left\lfloor(1-\alpha)\left\lfloor(1-\alpha)y\right\rfloor\right\rfloor$，转化求证： $$ \begin{align*} \gamma_x=\frac{u}{u+b}&\ge\alpha\newline \frac{1}{1+\left\lfloor(1-\alpha)\left\lfloor(1-\alpha)\left\lfloor\frac{2}{a}\right\rfloor-2\right\rfloor\right\rfloor}&\ge\alpha \end{align*} $$ 虽然这个我也不会解，但这个的解集比刚刚的好看了一些，只有 $\alpha>\frac{2}{11}$ 了。  （最后一位和 $\frac{2}{11}$ 不一样应该是因为四舍五入）

综合刚刚的一坨东西，这整个部分对 \alpha 的限制为 \alpha>\frac{2}{11}。

小幕后：

😡😡😡

接下来的都可以直接搞非常容易，代值就不强调了，速通一手。

\gamma_x\le1-\alpha

转换求证：

解得 \alpha\le1-\frac{\sqrt{2}}{2}。

\alpha\le\gamma_y\le 1-\alpha

解得 \alpha\le\frac{3-\sqrt{5}}{2}。

\alpha\le\gamma_z\le 1-\alpha

解得在我们讨论的值域内对 \alpha 无限制😕。

2.2.4 机甲合体！

把不合法的范围在 desmos 上标出（标合法的叠成一坨看不清）：

由于这标的是不合法的，所以实际上 \alpha 的范围为 \frac{2}{11}<\alpha\le1-\frac{\sqrt{2}}{2}。

3 合并相关证明

实际上如果你认真阅读了 OI-wiki 的证明过程会发现它有许多处上/下限既能用 \alpha 写又能用 \beta 写的地方都写了 \beta，以此推导出了 \beta 的范围。

但实际上，既然已经在证明旋转时将 \beta 代入，不论证明合并时 \beta 取值再严谨，整个证明仍然是关于 \beta=\frac{1}{2-\alpha} 的特例的证明。

综上，以下不同于 OI-wiki 将直接代入 \beta=\frac{1}{2-\alpha} 进行证明。

3.1 合并后平衡证明

显然 x 和 y 平衡时我们合并后会平衡（？），接下来钦定 y 过轻（即 1-\alpha<\frac{x}{x+y}），然后又有：

所以 z 不会过重，我们又发现如果 \rho_{y+w+z} 平衡那么我们合并后也会平衡（？），所以接下来只考虑 z 过轻的情况，即 z<\alpha(x+y)。

3.1.1 单旋

即 c\le \frac{1}{2-\alpha}(w+y)，现在证明旋转后 z 和 c、z+c 和 d 互相平衡。

因为我们对 y,w 用函数合并过，所以这里归纳地认为 y+w 是平衡的，那么：

虽然求出了范围，但是 z 范围中有 x+y，刚刚的范围中又有 w+y 很烦对不对，考虑它们的关系，发现 w+y=x+y-z，于是：

z 和 c 平衡

这里显然是可以把 x+y 后解不等式的，解出来是一个相当魔怔的三次根式结果😨：

z+c 和 d 平衡

这个解出来是 \alpha\le 1-\frac{\sqrt{2}}{2}。

3.1.2 双旋

即 \frac{1}{2-\alpha}(w+y)<c，现在证明旋转后 z 和 b、a 和 d、z+b 和 a+d 互相平衡。

使用几乎和单旋一样的证明可以得到：

然后由于 a 和 b 是平衡的，所以有：

z 和 b 平衡

这个解出来是 \alpha\le 1-\frac{\sqrt{2}}{2}。

a 和 d 平衡

右边的不等式解出来是对 \alpha 无限制，但是左边的就不好搞了：

证不出来的原因是解变量范围的时候放缩用力过猛了，但我们可以进行一些手法，因为 a 和 c 平衡，c\le \frac{1}{2-\alpha}(w+y)：

解出来是对 \alpha 无限制。

z+b 和 a+d 平衡

这个解出来又是一个三次根式：

有没有觉得很眼熟？没错，右边的不等式经过化简和单旋的那个不等式是等价的。

3.1.3 机甲合体！

把刚刚的所有解集交一起是 \alpha \le 1-\frac{\sqrt 2}{2}，这显然包含了 \frac{2}{11}<\alpha\le1-\frac{\sqrt{2}}{2}。

3.2 合并复杂度证明

最容易的一集，先证个引理：对于 x 过小的 y 在 x 递归到左子树后不会变得过大，这是因为一个 >\frac{1-\alpha}{\alpha}y 的值变为 <\frac{\alpha}{1-\alpha} y 需要乘小于 (\frac{\alpha}{1-\alpha})^2，然而可悲的是一次递归最小使权值乘以 \alpha，在 \frac{2}{11}<\alpha\le1-\frac{\sqrt{2}}{2} 时这是大于 (\frac{\alpha}{1-\alpha})^2 的。

又由于每往下一层至少让权值乘 1-\alpha，所以我们只需要往下递归 \log_{1-\alpha}\frac{x}{y} 次即可让 x 和 y 平衡，复杂度为 O(\log\frac{x}{y})。

4 分裂相关证明

这里只讨论从左子树中割的情况。

分类讨论 v 和 b 的大小：

总复杂度：O(\sum 1+\sum \log \frac{v}{b})，大力放缩考虑下一层的 v 必然不大于这一层的 b，往大估就可以抵消，没消的那个分母干脆扔了，这样复杂度最后变成了 O(\sum1+\log{v})，而递归至多 \log n 次，所以合并总复杂度就是 O(\log_n) 的。

5 完整代码

::::info[普通平衡树]

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace kong{bool st;}
namespace zhu{
int n;
struct WBLT{
const double alpha=0.292;
int st[2002000],top,cnt,rt;
struct{
    int val,siz,ch[2];
}tr[2002000];
#define ch(p,x) tr[x].ch[p]
#define val(x) tr[x].val
#define sz(x) tr[x].siz
void up(int x){
    sz(x)=sz(ch(0,x))+sz(ch(1,x));
    val(x)=val(ch(1,x));
}
int nw(int v=0){
    int x=top?st[top--]:++cnt;
    sz(x)=ch(0,x)=ch(1,x)=0;
    val(x)=v;
    sz(x)=1;
    return x;
}
void del(int &x){
    st[++top]=x;
    x=0;
}
int join(int x,int y){
    int z=nw();
    ch(0,z)=x;
    ch(1,z)=y;
    up(z);
    return z;
}
pair<int,int> cut(int &x){
    int l=ch(0,x),r=ch(1,x);
    del(x);
    return {l,r};
}
void rotate(int &x,bool fl){
    int a,b,c,d;
    tie(a,b)=cut(x);
    if(fl){
        tie(c,d)=cut(b);
        x=join(join(a,c),d);
    }
    else{
        tie(c,d)=cut(a);
        x=join(c,join(d,b));
    }
}
bool heavy(int x,int y){
    return y<alpha*(x+y);
}
bool nedtwo(int x,bool fl){
    return sz(ch(fl,x))>sz(x)/(2-alpha);
}
void balance(int &x){
    if(sz(x)==1) return;
    bool fl=sz(ch(1,x))>sz(ch(0,x));
    if(!heavy(sz(ch(fl,x)),sz(ch(!fl,x)))) return;
    if(nedtwo(ch(fl,x),!fl)){
        rotate(ch(fl,x),!fl);
    }
    rotate(x,fl);
}
void insert(int &x,int v){
    if(!x){
        x=nw(v);
        return;
    }
    if(sz(x)==1){
        bool fl=v>=val(x);
        ch(fl,x)=nw(v);
        ch(!fl,x)=nw(val(x));
        up(x);
        return; 
    }
    bool fl=v>val(ch(0,x));
    insert(ch(fl,x),v);
    up(x);
    balance(x);
}
void insert(int v){
    insert(rt,v);
}
void remove(int &x,int v){
    if(!x) return;
    if(sz(x)==1){
        if(val(x)==v) del(x);
        return;
    }
    bool fl=v>val(ch(0,x));
    remove(ch(fl,x),v);
    if(!ch(fl,x)){
        x=ch(!fl,x);
    }
    else{
        up(x);
        balance(x);
    }
}
void remove(int v){
    remove(rt,v);
}
int rk(int x,int v){
    if(!x) return 0;
    int ans=0;
    while(sz(x)>1){
        if(val(ch(0,x))<v){
            ans+=sz(ch(0,x));
            x=ch(1,x);
        }
        else{
            x=ch(0,x);
        }
    }
    return ans+(val(x)<v?1:0);
}
int rk(int v){return rk(rt,v)+1;}
int kth(int x,int k){
    while(sz(x)>1){
        if(sz(ch(0,x))>=k){
            x=ch(0,x);
        }
        else{
            k-=sz(ch(0,x));
            x=ch(1,x);
        }
    }
    return val(x);
}
int kth(int k){
    if(k>sz(rt)||k<=0) return -1;
    return kth(rt,k);
}
int pre(int v){
    return kth(rk(v)-1);
}
int nxt(int v){
    return kth(rk(v+1));
}
}Rs;
string main(){
//  freopen("P3369_14.in","r",stdin);
//  freopen("my.txt","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        int opt,x;
        cin>>opt>>x;
        if(opt==1) /*cout<<"in1"<<endl,*/Rs.insert(x)         /*,cout<<"out1"<<endl*/;
        if(opt==2) /*cout<<"in2"<<endl,*/Rs.remove(x)         /*,cout<<"out2"<<endl*/;
        if(opt==3) /*cout<<"in3"<<endl,*/cout<<Rs.rk(x)<<'\n' /*,cout<<"out3"<<endl*/;
        if(opt==4) /*cout<<"in4"<<endl,*/cout<<Rs.kth(x)<<'\n'/*,cout<<"out4"<<endl*/;
        if(opt==5) /*cout<<"in5"<<endl,*/cout<<Rs.pre(x)<<'\n'/*,cout<<"out5"<<endl*/;
        if(opt==6) /*cout<<"in6"<<endl,*/cout<<Rs.nxt(x)<<'\n'/*,cout<<"out6"<<endl*/;
//      if(Rs.Cnt%1000==0){
//          cerr<<i<<" "<<Rs.Cnt<<" "<<Rs.cnt<<" "<<Rs.sz(Rs.rt)<<" "<<Rs.dep(Rs.rt)<<endl;
//          Rs.Cnt++;
//      }
    }
    return "WBLT 我来了！";
}
} 
namespace kong{bool ed;double MB(){return (&st-&ed)/1048576.0;}}
signed main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    cerr<<zhu::main()<<'\n'<<kong::MB();
    return 0;
}

::::

::::info[文艺平衡树]

#include<bits/stdc++.h>
using namespace std;
namespace kong{bool st;}
namespace zhu{
int n,m;
struct WBLT{
const double alpha=0.292;
int st[200200],top,cnt,rt;
struct{
    int val,siz,ch[2],lazy;
}tr[200200];
#define ch(x,p) tr[x].ch[p]
#define lz(x) tr[x].lazy
#define val(x) tr[x].val
#define dep(x) tr[x].dep
#define sz(x) tr[x].siz
void up(int x){
    sz(x)=sz(ch(x,0))+sz(ch(x,1));
    val(x)=val(ch(x,1));
}
void dw(int x){
    if(lz(x)){
        swap(ch(x,0),ch(x,1));
        lz(ch(x,0))^=1;
        lz(ch(x,1))^=1;
        lz(x)=0;
    }
}
int nw(){
    int x=top?st[top--]:++cnt;
    sz(x)=val(x)=ch(x,0)=ch(x,1)=0;
    return x;
}
void del(int &x){
    st[++top]=x;
    x=0;
}
int nw_(int v){
    int x=nw();
    val(x)=v;
    sz(x)=1;
    return x;
}
int join(int x,int y){
    int z=nw();
    ch(z,0)=x;
    ch(z,1)=y;
    up(z);
    return z;
}
pair<int,int> cut(int &x){
    dw(x);
    int l=ch(x,0),r=ch(x,1);
    del(x);
    return {l,r};
}
void rotate(int &x,bool fl){
    int a,b,c,d;
    tie(a,b)=cut(x);
    if(fl){
        tie(c,d)=cut(b);
        x=join(join(a,c),d);
    }
    else{
        tie(c,d)=cut(a);
        x=join(c,join(d,b));
    }
}
bool heavy(int x,int y){
    return y<alpha*(x+y);
}
bool nedtwo(int x,bool fl){
    return sz(ch(x,!fl))>sz(x)/(2-alpha);
}
void balance(int &x){
    if(sz(x)==1) return;
    dw(x);
    bool fl=sz(ch(x,1))>sz(ch(x,0));
    if(!heavy(sz(ch(x,fl)),sz(ch(x,!fl)))) return;
    dw(ch(x,fl));
    if(nedtwo(ch(x,fl),fl)){
        dw(ch(ch(x,fl),!fl));
        rotate(ch(x,fl),!fl);
    }
    rotate(x,fl);
}
int merge(int x,int y){
    if(!x||!y) return x+y;
    int a,b;
    if(heavy(sz(x),sz(y))){
        tie(a,b)=cut(x);
        int z=join(a,merge(b,y));
        balance(z);
        return z;
    }
    else if(heavy(sz(y),sz(x))){
        tie(a,b)=cut(y);
        int z=join(merge(x,a),b);
        balance(z);
        return z;
    }
    else{
        return join(x,y);
    }
}
pair<int,int> split(int x,int k){
    if(!x) return {0,0};
    if(!k) return {0,x};
    if(k==sz(x)) return {x,0};
    int a,b,c,d;
    tie(a,b)=cut(x);
    if(k<=sz(a)){
        tie(c,d)=split(a,k);
        return {c,merge(d,b)};
    }
    else{
        tie(c,d)=split(b,k-sz(a));
        return {merge(a,c),d};
    }
}
void reverse(int l,int r){
    int a,b;
    tie(rt,b)=split(rt,r);
    tie(a,rt)=split(rt,l-1);
    lz(rt)^=1;
    rt=merge(a,merge(rt,b));
}
int build(int l,int r){
    if(l==r){
        return nw_(l);
    }
    int mid=(l+r)>>1;
    return merge(build(l,mid),build(mid+1,r));
}
void out(int x){
    if(sz(x)==1){
        cout<<val(x)<<" ";
        return;
    }
    dw(x);
    out(ch(x,0));
    out(ch(x,1));
}
}Rs;
string main(){
    cin>>n>>m;
    Rs.rt=Rs.build(1,n);
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        Rs.reverse(l,r);
    }
    Rs.out(Rs.rt);
    cout<<"\n";
    return "WBLT 我来了！";
}
} 
namespace kong{bool ed;double MB(){return (&st-&ed)/1048576.0;}}
signed main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    cerr<<zhu::main()<<'\n'<<kong::MB();
    return 0;
}

::::