题解 P2596 【[ZJOI2006]书架】

· · 题解

无旋treap做法

无旋treap可以维护一棵树的中序遍历结果.但是不支持通过编号来找节点.于是在无旋treap的基础上,我维护了每个节点的父亲,这样就可以求出一个节点是中序遍历中的第几个.

那么对于一个节点,每次将它向树根跳,如果它是右儿子,那么就将它父亲的左子树的值以及父亲的大小计入结果.

那么问题就只有如何记录父亲了.显然会改变父亲的只有split和merge操作,那么我只需要在这两个函数中修改就可以了.在split的时候再传两个参数记录父亲,merge在修改儿子的时候同时将父亲一起修改.

其他的都是无旋treap的基本操作了.

代码凑合着看一下吧.

#include<bits/stdc++.h>
#define debug out(root), cout << endl
using namespace std;
const int N=80000+5;

int n, m, id[N], a[N], root, r1, r2, r3, r4, cnt = 0;
//id记录某一个书的编号映射到树中的节点编号

struct treap{
    int ch[2], fa, size, rd, val;
}t[N];

int gi(){
    int ans = 0, f = 1; char i = getchar();
    while(i<'0' || i>'9'){ if(i == '-') f = -1; i = getchar(); }
    while(i>='0' && i<='9') ans = ans*10+i-'0', i = getchar();
    return ans * f;
}

int newnode(int val){
    t[++cnt].val = val; t[cnt].rd = rand(), t[cnt].size = 1;
    id[val] = cnt; return cnt;
}

void up(int x){ t[x].size = t[t[x].ch[0]].size+t[t[x].ch[1]].size+1; }

void split(int x, int k, int &a, int &b, int faa = 0, int fab = 0){
    //传两个父亲节点的参数是为了防止记录父亲出问题.
    //因为父亲记录儿子的时候是通过取地址传参修改的
    //而两颗子树记录的父亲是分开的
    if(x == 0){ a = b = 0; return; }
    if(k <= t[t[x].ch[0]].size) t[x].fa = fab, b = x, split(t[x].ch[0], k, a, t[x].ch[0], faa, x);
    else t[x].fa = faa, a = x, split(t[x].ch[1], k-t[t[x].ch[0]].size-1, t[x].ch[1], b, x, fab); up(x);
}

int merge(int x, int y){
    if(x == 0 || y == 0) return x+y;
    //直接在记录儿子的时候同时修改父亲
    if(t[x].rd < t[y].rd){
        t[x].ch[1] = merge(t[x].ch[1], y);
        t[t[x].ch[1]].fa = x; up(x); return x;
    }
    else {
        t[y].ch[0] = merge(x, t[y].ch[0]);
        t[t[y].ch[0]].fa = y; up(y); return y;
    }
}

void insert(int pos, int val){
    split(root, pos, r1, r2);
    root = merge(r1, merge(newnode(val), r2));
}

bool get(int x){ return t[t[x].fa].ch[1] == x; }

int find(int cnt){//cnt是节点编号
    int node = cnt, res = t[t[cnt].ch[0]].size+1;
    while(node != root && cnt){
        if(get(cnt)) res += t[t[t[cnt].fa].ch[0]].size+1;
        cnt = t[cnt].fa;
        //这里可以画图理解一下,因为如果该节点是左儿子的话,向上走是中序遍历在增大的
        //如果是右儿子向上跳的话,父亲的左子树的所有节点的中序遍历的结果都小于我在查的节点,所以要计入答案.
    }
    return res;
}

int main(){
    char opt[10]; int x, y, k; n = gi(), m = gi(); srand(19260817);
    for(int i=1;i<=n;i++) a[i] = gi(), insert(i-1, a[i]);
    for(int i=1;i<=m;i++){
        scanf("%s", opt); x = gi();

        if(opt[0] == 'T'){
            k = find(id[x]);//通过节点编号找到书本编号为x的节点是第k个
            split(root, k, r1, r3);
            split(r1, k-1, r1, r2);
            root = merge(r2, merge(r1, r3));
        }

        if(opt[0] == 'B'){
            k = find(id[x]);
            split(root, k, r1, r3, 0);
            split(r1, k-1, r1, r2, 0);
            root = merge(r1, merge(r3, r2));
        }

        if(opt[0] == 'I'){
            y = gi(); k = find(id[x]);
            if(y){
                if(y > 0){//与前驱/后继交换后插入
                    split(root, k+1, r3, r4);
                    split(r3, k, r2, r3);
                    split(r2, k-1, r1, r2);
                    root = merge(r1, merge(r3, merge(r2, r4)));
                }
                else {
                    split(root, k, r3, r4);
                    split(r3, k-1, r2, r3);
                    split(r2, k-2, r1, r2);
                    root = merge(r1, merge(r3, merge(r2, r4)));
                }
            }
        }

        if(opt[0] == 'A'){
            k = find(id[x]);
            printf("%d\n", k-1);
        }

        if(opt[0] == 'Q'){
            split(root, x, r1, r2);
            int node = r1;
            while(t[node].ch[1]) node = t[node].ch[1];
            printf("%d\n", t[node].val);
            root = merge(r1, r2);
        }
    }
    return 0;
}