题面

LOJ传送门

题解

直接想办法模拟。

找找性质。

发现插入就是在前驱和后继找一个深度大的接在下面。简单推一推可以证明。

然后把最小值旋到根，假设最小值为\(x\)，\(x\)肯定没有左子树。然后旋到根后右子树所有点深度无变化，\(x\)深度变为\(1\)，剩下的点深度减一。比较显然。

最大值同理。

那么离散化后用树状数组维护深度，需要支持区间修改，单点修改，单点查询。想知道子树的节点编号，首先发现子树肯定是一段连续的编号（数值不一定连续，在所有有效的数中的相对位置连续），那么子树节点编号一定在\(x\)和\(fa_x\)编号之间（\(x\)现在是最大/小值，只有一个子树），那么就是区间\((x,fa_x)\)深度不变或者区间\((fa_x,x)\)深度不变，其他位置（补集）深度减一就行了，\(x\)单点修改为\(1\)。

新插入一个点必须消除之前的区间操作带来的影响。就先查询，然后单点改一下就行了。

找前驱和后继用set就行了。

CODE

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef set<int>::iterator sit;
const int MAXN = 100005;
int n, op[MAXN], a[MAXN], fa[MAXN], ch[MAXN][2], T[MAXN];
int b[MAXN], tot, rt;
set<int>s;
inline void upd(int x, int v) {
    while(x <= tot) T[x] += v, x += x&-x;
}
inline int dep(int x) {
    int re = 0; while(x) re += T[x], x -= x&-x; return re;
}
int main () {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &op[i]);
        if(op[i] == 1) scanf("%d", &a[i]), b[++tot] = a[i];
    }
    sort(b + 1, b + tot + 1);
    for(int i = 1; i <= n; ++i) {
        if(op[i] == 1) {
            int x = lower_bound(b + 1, b + tot + 1, a[i]) - b;
            s.insert(x);
            sit it = s.lower_bound(x);
            int f = 0;
            if(it != s.begin()) {
                --it; int tmp = (*it);
                if(!f || dep(tmp) > dep(f)) f = tmp;
                ++it;
            }
            if((++it) != s.end()) {
                int tmp = (*it);
                if(!f || dep(tmp) > dep(f)) f = tmp;
            }
            fa[x] = f;
            if(f)ch[f][x>f] = x;
            else rt = x;
            int tmp=dep(f)+1-dep(x);
            upd(x, tmp);
            upd(x+1, -tmp);
            printf("%d\n", dep(x));
        }
        else if(op[i]&1) {
            sit it = s.end(); --it;
            int x = (*it), y = fa[x];
            printf("%d\n", dep(x));
            if(y) {
                int tmp = 1-dep(x);
                upd(x, tmp);
                upd(x+1, -tmp);
                upd(1, 1);
                upd(y+1, -1);
                if(ch[x][0])fa[ch[x][0]] = y; if(y)ch[y][1] = ch[x][0]; ch[x][0] = fa[x] = 0;
                if(rt) fa[rt] = x, ch[x][0] = rt; rt = x;
            }
            if(op[i] > 3) {
                rt = ch[x][0]; ch[x][0] = 0;
                fa[rt] = 0;
                s.erase(x), upd(1, -1);
            }
        }
        else {
            sit it = s.begin();
            int x = (*it), y = fa[x];
            printf("%d\n", dep(x));
            
            if(y) {
                int tmp = 1-dep(x);
                upd(x, tmp);
                upd(x+1, -tmp);
                upd(y, 1);
                if(ch[x][1])fa[ch[x][1]] = y; ch[y][0] = ch[x][1];
                ch[x][1] = fa[x] = 0;
                if(rt) fa[rt] = x, ch[x][1] = rt; rt = x;
            }
            if(op[i] > 3) {
                rt = ch[x][1]; ch[x][1] = 0;
                fa[rt] = 0;
                s.erase(x), upd(1, -1);
            }
        }
    }
}

[AH2017/HNOI2017]单旋（用树状数组和set 模拟平衡树）

原文：https://www.cnblogs.com/Orz-IE/p/12088464.html