ZJOI2006 书架

发表于 分类于

$Problem’s$ $Website$

ZJOI2006 书架

$Solution$

这道题是一道平衡树好题，我暂时不会$Splay$，所以就用$fhq-Treap$做。

这道题就要用到排名分裂了。

也就是以排名为对象进行分裂。

对这道题来说，排名就相当于当前这本书上有几本书。

特殊地一点：用一个数组将书的编号映射到树中的编号。

因此，我们还要记录每个节点的父亲节点。

我们来详细解释一下题目中操作的步骤：

1.$Top$ 对$now$和$now - 1$进行分裂，然后将当前的书放到最顶上。

2.$Bottom$ 类似于第一个操作，只不过要把当前的数放到最底下。

3.$Insert$

如果是$0$，那么不需要管。

如果是$1$，就把当前的书和它的前驱交换一下。

如果是$-1$,就把当前的书和它的后驱交换一下。

4.$Ask$ 我们直接查找对应的排名，但注意答案要$-1$，因为树的编号是从$1$开始的。

5.$Query$ 对$x$进行分裂，分裂后左边的数的最右子树的值即为答案。

$P.s.$ 如何使用映射数组找到编号为$x$的书在树中的排名？

$Answer$：我们在确保当前书的编号不为树的根时向上走，如果当前节点是其父节点的右子树，答案就加上左子树的排名$+1$，大家可以画个图感性理解一下或者运用人类智慧进行理解。

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//Coded by dy.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
#define gc getchar()
#define pc(x) putchar(x)
#define re register
using std :: cerr;
using std :: endl;
const int Maxn = 80000 + 10;
inline int sc() {
    int xx = 0, ff = 1; char cch = gc;
    while(!isdigit(cch)) {
        if(cch == '-') ff = -1; cch = gc;
    }
    while(isdigit(cch)) {
        xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
    }
    return xx * ff;
}
inline void out(int x) {
    if(x < 0)
		pc('-'), x = -x;
    if(x >= 10)
        out(x / 10);
    pc(x % 10 + '0');
}
struct fhq_Treap {
	int ch[2];
	int fa, siz, val, dat;
}t[Maxn];
int n, m;
int rt, r1, r2, r3, r4, tot;
int id[Maxn];
inline void pushup(int id) {
	t[id].siz = t[t[id].ch[0]].siz + t[t[id].ch[1]].siz + 1;
}
inline int cre(int r) {
	t[++tot].siz = 1, t[tot].val = r, t[tot].dat = rand(), id[r] = tot;
	return tot;
}
inline void split(int id, int r, int &x, int &y, int faa = 0, int fab = 0) {
    if(!id)
    	x = y = 0;
    else {
    	if(r <= t[t[id].ch[0]].siz) {
    		t[id].fa = fab, y = id;
    		split(t[id].ch[0], r, x, t[id].ch[0], faa, id);
		}
		else {
			t[id].fa = faa, x = id;
			split(t[id].ch[1], r - t[t[id].ch[0]].siz - 1, t[id].ch[1], y, id, fab);
		}
		pushup(id);
	}
}
inline int merge(int x, int y) {
    if(!x || !y)
		return x + y;
    if(t[x].dat < t[y].dat) {
        t[x].ch[1] = merge(t[x].ch[1], y);
        t[t[x].ch[1]].fa = x;
		pushup(x);
		return x;
    }
    t[y].ch[0] = merge(x, t[y].ch[0]);
    t[t[y].ch[0]].fa = y;
	pushup(y);
	return y;
}
inline void insert(int r, int id) {
	split(rt, r, r1, r2);
	rt = merge(r1, merge(cre(id), r2));
}
inline bool get(int x) {
	return t[t[x].fa].ch[1] == x;
}
inline int find_id(int cnt) {
    int node = cnt, res = t[t[cnt].ch[0]].siz + 1;
    while(node != rt && cnt){
        if(get(cnt))
			res += t[t[t[cnt].fa].ch[0]].siz+1;
        cnt = t[cnt].fa;
    }
    return res;
}
int main() {
	srand(20041029);
	n = sc(), m = sc();
	for(re int i = 1; i <= n; ++i)
		insert(i - 1, sc());
//	cerr << rt << endl;
	while(m--) {
		char c[7];
		scanf("%s", c);
		int x = sc();
		if(c[0] == 'T') {
			int now = find_id(id[x]);
//			cerr << now << endl;
			split(rt, now, r1, r3);
			split(r1, now - 1, r1, r2);
//			cerr <<rt << " " << r2 << " " << r1 << " " << r3 << endl;
			rt = merge(r2, merge(r1, r3));
		}
		else if(c[0] == 'B') {
			int now = find_id(id[x]);
//			cerr << now << endl;
			split(rt, now, r1, r3, 0);
            split(r1, now - 1, r1, r2, 0);
//            cerr << rt << " " << r1 << " " << r2 << " " << r3 << endl;
            rt = merge(r1, merge(r3, r2));
		}
		else if(c[0] == 'I') {
			int y = sc(), now = find_id(id[x]);
			if(y == 1) {
				split(rt, now + 1, r3, r4);
				split(r3, now, r2, r3);
				split(r2, now - 1, r1, r2);
				rt = merge(r1, merge(r3, merge(r2, r4)));
			}
			else if(y == -1) {
				split(rt, now, r3, r4);
				split(r3, now - 1, r2, r3);
				split(r2, now - 2, r1, r2);
				rt = merge(r1, merge(r3, merge(r2, r4)));
			}
		}
		else if(c[0] == 'A') {
			int now = find_id(id[x]);
			out(now - 1), pc('\n');
		}
		else {
			split(rt, x, r1, r2);
			int node = r1;
			while(t[node].ch[1])
				node = t[node].ch[1];
			out(t[node].val), pc('\n');
			rt = merge(r1, r2);
		}
	}
    return 0;
}

$rp++$