Chlience

【题解】LOJ 2018 「AHOI / HNOI2017」单旋
Problem对一个数据结构 Spaly 维护五个操作:插入单旋最小值单旋最大值单旋删除最小值单旋删除最大值Tho...
扫描右侧二维码阅读全文
08
2019/02

【题解】LOJ 2018 「AHOI / HNOI2017」单旋

Problem

对一个数据结构 Spaly 维护五个操作:

  1. 插入
  2. 单旋最小值
  3. 单旋最大值
  4. 单旋删除最小值
  5. 单旋删除最大值

Thought

插入:其前驱后继在原序列中肯定是相邻的,那么在树上必然有直接的祖先关系,成为较深的节点左/右儿子即可(必然是空的)

单旋最小值:单旋树上最靠左的节点,不改变树的形态,该点深度变为一,右子树深度不变,其他点深度加一
单旋最大值:单旋树上最靠右的节点,不改变树的形态,该点深度变为一,左子树深度不变,其他点深度加一

单旋删除最小值:单旋最小值后所有点深度减一
单旋删除最大值:单旋最大值后所有点深度减一

因为仅仅单旋最小值或者最大值,其右/左子树具有特殊的性质:在原序列上是连续的一段,恰好夹在该点和该点父亲之间

利用线段树维护每个点的深度,set 维护每个点的前驱后继即可

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
#define L (x << 1)
#define R (x << 1 | 1)
#define mid ((l + r) >> 1)
struct Tree {
    int dep[N << 2];
    void change(int x, int l, int r, int ll, int rr, int p) {
        if(ll > rr) return;
        if(l >= ll && r <= rr)
            dep[x] += p;
        else {
            if(mid >= ll) change(L, l, mid, ll, rr, p);
            if(mid < rr) change(R, mid + 1, r, ll, rr, p);
        }
    }
    void pushdown(int x) {
        dep[L] += dep[x];
        dep[R] += dep[x];
        dep[x] = 0;
    }
    void change(int x, int l, int r, int pos, int p) {
        if(l == r)
            dep[x] = p;
        else {
            pushdown(x);
            if(pos <= mid) change(L, l, mid, pos, p);
            else change(R, mid + 1, r, pos, p);
        }
    }
    int query(int x, int l, int r, int pos) {
        if(l == r)
            return dep[x];
        else {
            pushdown(x);
            if(pos <= mid) return query(L, l, mid, pos);
            else return query(R, mid + 1, r, pos);
        }
    }
}t;
set <int> S;
set <int> :: iterator it, itp, itn;
int m;
int key[N], K[N], opt[N], cnt;
int fa[N], ch[N][2], rt;
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in", "r", stdin);
    #endif
    m = read();
    for(int i = 1; i <= m; ++ i) {
        opt[i] = read();
        if(opt[i] == 1) {
            key[i] = read();
            K[++ cnt] = key[i];
        }
    }
    sort(K + 1, K + cnt + 1);
    cnt = unique(K + 1, K + cnt + 1) - K - 1;
    for(int i = 1; i <= m; ++ i)
        key[i] = lower_bound(K + 1, K + cnt + 1, key[i]) - K;
    for(int i = 1; i <= m; ++ i) {
        if(opt[i] == 1) {
            S.insert(key[i]);
            if(!rt) {
                rt = key[i];
                t.change(1, 1, cnt, key[i], 1);
                printf("1\n");
                continue;
            }
            int pre = - 1, nxt = - 1;
            itp = itn = it = S.find(key[i]);
            if(itp != S.begin()) {
                -- itp;
                pre = *itp;
            }
            ++ itn;
            if(itn != S.end())
                nxt = *itn;
            int depth = 0, f = 0;
            if(pre != - 1) {
                int dep = t.query(1, 1, cnt, pre);
                if(dep > depth) {
                    depth = dep;
                    f = pre;
                }
            }
            if(nxt != -1) {
                int dep = t.query(1, 1, cnt, nxt);
                if(dep > depth) {
                    depth = dep;
                    f = nxt;
                }
            }
            fa[key[i]] = f; 
            if(f == pre)
                ch[pre][1] = key[i];
            else
                ch[nxt][0] = key[i];
            t.change(1, 1, cnt, key[i], depth + 1);
            printf("%d\n", depth + 1);
        }
        else if(opt[i] == 2) {
            it = S.begin();
            int now = *it;
            if(rt == now) {
                printf("1\n");
                continue;
            }
            printf("%d\n", t.query(1, 1, cnt, now));
            t.change(1, 1, cnt, 1, cnt, 1);
            t.change(1, 1, cnt, now + 1, fa[now] - 1, - 1);
            t.change(1, 1, cnt, now, 1);
            if(ch[now][1]) {
                fa[ch[now][1]] = fa[now];
                ch[fa[now]][0] = ch[now][1];
            }
            fa[now] = 0;
            ch[now][1] = rt;
            fa[rt] = now;
            rt = now;
        }
        else if(opt[i] == 3) {
            it = S.end(); -- it;
            int now = *it;
            if(rt == now) {
                printf("1\n");
                continue;
            }
            printf("%d\n", t.query(1, 1, cnt, now));
            t.change(1, 1, cnt, 1, cnt, 1);
            t.change(1, 1, cnt, fa[now] + 1, now - 1, - 1);
            t.change(1, 1, cnt, now, 1);
            if(ch[now][0]) {
                fa[ch[now][0]] = fa[now];
                ch[fa[now]][1] = ch[now][0];
            }
            fa[now] = 0;
            ch[now][0] = rt;
            fa[rt] = now;
            rt = now;
        }
        else if(opt[i] == 4) {
            it = S.begin();
            int now = *it;
            S.erase(it);
            if(rt == now) {
                printf("%d\n", 1);
                rt = ch[now][1];
                fa[ch[now][1]] = 0;
                t.change(1, 1, cnt, 1, cnt, - 1);
                t.change(1, 1, cnt, now, 0);
                continue;
            }
            printf("%d\n", t.query(1, 1, cnt, now));
            t.change(1, 1, cnt, now + 1, fa[now] - 1, - 1);
            t.change(1, 1, cnt, now, 0);
            if(ch[now][1]) {
                fa[ch[now][1]] = fa[now];
                ch[fa[now]][0] = ch[now][1];
            }
            fa[now] = ch[now][0] = ch[now][1] = 0;
        }
        else {
            it = S.end(); -- it;
            int now = *it;
            S.erase(it);
            if(rt == now) {
                printf("%d\n", 1);
                rt = ch[now][0];
                fa[ch[now][0]] = 0;
                t.change(1, 1, cnt, 1, cnt, - 1);
                t.change(1, 1, cnt, now, 0);
                continue;
            }
            printf("%d\n", t.query(1, 1, cnt, now));
            t.change(1, 1, cnt, fa[now] + 1, now - 1, - 1);
            t.change(1, 1, cnt, now, 0);
            if(ch[now][0]) {
                fa[ch[now][0]] = fa[now];
                ch[fa[now]][1] = ch[now][0];
            }
            fa[now] = ch[now][0] = ch[now][1] = 0;
        }
    }
    return 0;
}
Last modification:February 8th, 2019 at 06:43 pm

Leave a Comment