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$

//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++$