BZOJ1861: [Zjoi2006]Book 书架

Description

小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上面就只可能有X-1、X或X+1本书。当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。久而久之，小T的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：(1)编号为X的书在书柜的什么位置；(2)从上到下第i本书的编号是多少。

Input

第一行有两个数n，m，分别表示书的个数以及命令的条数；第二行为n个正整数：第i个数表示初始时从上至下第i个位置放置的书的编号；第三行到m+2行，每行一条命令。命令有5种形式： 1． Top S——表示把编号为S的书房在最上面。 2． Bottom S——表示把编号为S的书房在最下面。 3． Insert S T——T∈{-1，0，1}，若编号为S的书上面有X本书，则这条命令表示把这本书放回去后它的上面有X+T本书； 4． Ask S——询问编号为S的书的上面目前有多少本书。 5． Query S——询问从上面数起的第S本书的编号。

Output

对于每一条Ask或Query语句你应该输出一行，一个数，代表询问的答案。

Sample Input

10 10
1 3 2 7 5 8 10 4 9 6
Query 3
Top 5
Ask 6
Bottom 3
Ask 3
Top 6
Insert 4 -1
Query 5
Query 2
Ask 2

Sample Output

2
9
9
7
5
3

HINT

数据范围

100%的数据，n,m < = 80000

Solution

显然可以用fhqtreap按位置分裂来解决所有的操作。
但是要注意一个问题，fhqtreap按位置分裂那么序号就乱序了，不能在树上往下爬来找数的排名。
考虑对每个节点维护一个父指针，在插入的时候把数的位置记录下来（即这个数在treap中的编号）。
那么查询的时候，从当前节点往上爬，如果它是右儿子的话，证明左儿子及父亲都是它前面的数，一直爬到根就可以知道它是第几大了。然后就是正常的fhqtreap按位置分裂操作了（注意操作时是对这个数的pos操作，即对这个数在treap中的编号操作）。

#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define lc (t[rt].l)
#define rc (t[rt].r)
int n, m, root, tot, pos[N];
struct fhq { int l, r, siz, rnd, val, fa; } t[N];
void up(int rt) { 
    t[rt].siz = 1 + t[lc].siz + t[rc].siz; 
    t[lc].fa = t[rc].fa = rt;
}
void split(int rt, int &l, int &r, int k) {
    if(!k) l = 0, r = rt;
    else if(k == t[rt].siz) l = rt, r = 0;
    else if(k <= t[lc].siz) r = rt, split(lc, l, lc, k), up(rt);
    else l = rt, split(rc, rc, r, k - t[lc].siz - 1), up(rt);
}
void merge(int &rt, int l, int r) {
    if(!l || !r) rt = l + r;
    else if(t[l].rnd < t[r].rnd) rt = l, merge(rc, rc, r), up(rt);
    else rt = r, merge(lc, l, lc), up(rt);
}
int build(int v) {
    t[++tot] = (fhq) {0, 0, 1, rand()<<15|rand(), v, 0}; 
    return tot;
}
int find(int rt) {
    int rk = t[lc].siz + 1;
    while(t[rt].fa) {
        if(t[t[rt].fa].r == rt) rk += t[t[t[rt].fa].l].siz + 1;
        rt = t[rt].fa;
    }
    return rk;
}
void top(int s) {
    int x, y, tmp, rk = find(s);
    split(root, x, y, rk); split(x, x, tmp, rk - 1);
    merge(x, tmp, x); merge(root, x, y);
}
void down(int s) {
    int x, y, tmp, rk = find(s);
    split(root, x, y, rk); split(x, x, tmp, rk - 1);
    merge(root, x, y); merge(root, root, tmp);
}
void ins(int s, int t) {
    if(!t) return;
    int x, y, z, tmp, rk = find(s);
    split(root, x, y, rk); split(x, x, tmp, rk - 1);
    if(t == -1) {
        split(x, x, z, rk - 2); 
        merge(x, x, tmp); merge(x, x, z);
        merge(root, x, y);
    } else {
        split(y, z, y, 1);
        merge(x, x, z); merge(x, x, tmp); 
        merge(root, x, y);
    }
}
int ask(int s) {
    int x, y, ans, rk = find(s);
    split(root, x, y, rk - 1);
    ans = t[x].siz;
    merge(root, x, y);
    return ans;
}
int query(int s) {
    int x, y, ans, tmp;
    split(root, x, y, s); split(x, x, tmp, s - 1);
    ans = t[tmp].val;
    merge(x, x, tmp); merge(root, x, y);
    return ans; 
}
int main() {
    scanf("%d%d", &n, &m); char ch[10];
    for(int i = 1, x; i <= n; ++i) {
        scanf("%d", &x); pos[x] = i;
        merge(root, root, build(x));
    }
    for(int s, t, i = 1; i <= m; ++i) {
        scanf("%s%d", ch, &s);
        if(ch[0] == 'T') top(pos[s]);
        else if(ch[0] == 'B') down(pos[s]);
        else if(ch[0] == 'I') scanf("%d", &t), ins(pos[s], t);
        else if(ch[0] == 'A') printf("%d\n", ask(pos[s]));
        else printf("%d\n", query(s));
    }
}