题目地址：洛谷：【P2596】[ZJOI2006]书架 – 洛谷、BZOJ：Problem 1861. — [Zjoi2006]Book 书架

题目描述

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

输入输出格式

输入格式：
第一行有两个数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本书的编号。

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

输入输出样例

输入样例#1：

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

输出样例#1：

2
9
9
7
5
3

说明

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

题解

考虑使用Splay来维护这个序列。对于放在最上面的情况，我们考虑把S splay到根，此时只需要找到S的后继，也splay上来，并且把S的左子树接到后继节点的左子树位置上，就完成了。放在最下面类似操作。Insert操作可以考虑直接调换节点信息。Ask即询问左子树大小。Query就是一个排名询问。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'T' || c == 'B' || c == 'I' || c == 'A' || c == 'Q';
}

inline char readop() {
    char c;
    while(!isop(c = fgc()));
    return c;
}

const int MAXN = 80005, INF = 1e9;

struct Node {
    int fa, ch[2], val, siz;
} tr[MAXN];
int rt, spn[MAXN], tot;

inline void update(int p) {
    tr[p].siz = tr[tr[p].ch[0]].siz + tr[tr[p].ch[1]].siz + 1;
}

inline bool isleft(int p) {
    return tr[tr[p].fa].ch[0] == p;
}

inline void rotate(int p) {
    bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[p].fa = ffa; if(ffa) tr[ffa].ch[!isleft(fa)] = p;
    tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
    tr[fa].fa = p; tr[p].ch[!t] = fa;
    update(fa);
    if(!tr[p].fa) rt = p;
}

inline void splay(int p, int tar) {
    for(int fa = tr[p].fa; fa != tar; rotate(p), fa = tr[p].fa) {
        if(tr[fa].fa != tar) rotate(isleft(p) == isleft(fa) ? fa : p);
    }
    update(p);
}

inline int queryn(int p, int rk) {
    if(rk <= tr[tr[p].ch[0]].siz) {
        return queryn(tr[p].ch[0], rk);
    }
    rk -= tr[tr[p].ch[0]].siz;
    if(rk == 1) {
        splay(p, 0);
        return p;
    }
    rk--;
    return queryn(tr[p].ch[1], rk);
}

inline int querypre() {
    int p = tr[rt].ch[0];
    while(tr[p].ch[1]) p = tr[p].ch[1];
    return p;
}

inline int querynxt() {
    int p = tr[rt].ch[1];
    while(tr[p].ch[0]) p = tr[p].ch[0];
    return p;
}

inline void nodeswap(int p, int q) {
    std::swap(tr[p].val, tr[q].val);
    std::swap(spn[tr[p].val], spn[tr[q].val]);
}

inline void top(int p) {
    splay(p, 0);
    if(!tr[p].ch[0]) return;
    if(!tr[p].ch[1]) {
        std::swap(tr[p].ch[0], tr[p].ch[1]);
    }
    int q = querynxt();
    splay(q, p);
    tr[q].ch[0] = tr[p].ch[0];
    tr[tr[q].ch[0]].fa = q; 
    tr[p].ch[0] = 0;
    update(p); update(q);
}

inline void bottom(int p) {
    splay(p, 0);
    if(!tr[p].ch[1]) return;
    if(!tr[p].ch[0]) {
        std::swap(tr[p].ch[0], tr[p].ch[1]);
    }
    int q = querypre();
    splay(q, p);
    tr[q].ch[1] = tr[p].ch[1];
    tr[tr[q].ch[1]].fa = q;
    tr[p].ch[1] = 0;
    update(p); update(q);
}

int w[MAXN];

inline int build(int fa, int l, int r) {
    if(l > r) return 0;
    int p = ++tot, mid = (l + r) >> 1;
    tr[p].val = w[mid];
    spn[w[mid]] = p;
    tr[p].fa = fa;
    tr[p].ch[0] = build(p, l, mid - 1);
    tr[p].ch[1] = build(p, mid + 1, r);
    update(p);
    return p;
}

int n, m, s, t;
char op;

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) w[i] = readint();
    rt = build(0, 1, n);
    while(m--) {
        op = readop(); s = readint();
        if(op == 'T') {
            s = spn[s];
            top(s);
        } else if(op == 'B') {
            s = spn[s];
            bottom(s);
        } else if(op == 'I') {
            s = spn[s];
            t = readint();
            splay(s, 0);
            if(t == -1) {
                int q = querypre();
                nodeswap(s, q);
            } else if(t == 1) {
                int q = querynxt();
                nodeswap(s, q);
            }
        } else if(op == 'A') {
            s = spn[s];
            splay(s, 0);
            printf("%d\n", tr[tr[s].ch[0]].siz);
        } else {
            int q = queryn(rt, s);
            printf("%d\n", tr[q].val);
        }
    }
    return 0;
}