自动搬运

查看原文

来自洛谷，原作者为

	Brave_Cattle **

搬运于2025-08-24 21:39:27，当前版本为作者最后更新于2018-07-23 10:37:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

无旋treap做法

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

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

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

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

• $Top$: 提取该节点,放在树的最前面合并.
• $Bottom$: 提取节点,放在树的最后面合并.
• $Insert$: 将它与前驱/后继从整棵树中分离出来,交换顺序合并.
• $Ask$: 直接通过编号找到节点是中序遍历结果第几个.
• $Query$: 先找到节点是中序遍历第几个,然后split前k个,在分离出的第一颗子树中找最右边的节点.

代码凑合着看一下吧.

#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;
}