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 \in \{-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

Data Range

对于所有的数据, 满足 \(n, m \leq 80000\)

Explanation

本题可以用 Splay 水一发.

如果用 map 来维护一下书的编号和节点编号之间的对应关系, 直接就可以查询水 STL. 进一步, 其实这道题本质上和 poj3580 没有区别, 只不过是一道数据弱化版的题目.

Splay 写完 1A 好开心 (离 Splay with tree 又近了一步)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <map>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define range(_begin,_end) rep(_,_begin,_end)
using namespace std;
typedef long long lli;
const int maxn = 200100;
const int infinit = 10e7;

class SplayTree
{
public:
    int ch[maxn][2], par[maxn];
    int val[maxn], size[maxn];
    int root, ncnt;
    #define lc(__x) ch[__x][0]
    #define rc(__x) ch[__x][1]
    int make_node(int v)
    {
        int p = ++ncnt;
        lc(p) = rc(p) = par[p] = 0;
        val[p] = v; size[p] = 1;
        return p;
    }
    void rotate(int p)
    {
        int q = par[p], g = par[q];
        int x = p == rc(q), y = q == rc(g);
        ch[q][x] = ch[p][!x]; if (ch[q][x]) par[ch[q][x]] = q;
        ch[p][!x] = q; par[q] = p;
        if (g) ch[g][y] = p; par[p] = g;
        size[q] = size[lc(q)] + size[rc(q)] + 1;
        size[p] = size[lc(p)] + size[rc(p)] + 1;
        return ;
    }
    void splay(int p, int t)
    {
        for (int q = 0; (q = par[p]) && q != t; rotate(p))
            if (par[q] && par[q] != t)
                rotate((p == rc(q)) == (q == rc(par[q])) ? q : p);
        if (t == 0) root = p;
        return ;
    }
    int find_(int sz)
    {
        int p = root;
        while (p) {
            if (sz <= size[lc(p)]) {
                p = lc(p); continue; }
            sz -= size[lc(p)];
            if (sz == 1) return p;
            sz--; p = rc(p);
        }
        splay(p, 0);
        return p;
    }
    int find(int sz)
    {
        return find_(sz + 1);
    }
    int get_rank(int p)
    {
        splay(p, 0);
        return size[lc(root)];
    }
    int suc(int p)
    {
        if (!rc(p)) { while (p && p == rc(par[p])) p = par[p]; p = par[p]; }
        else { p = rc(p); while (p && lc(p)) p = lc(p); }
        return p;
    }
    int pre(int p)
    {
        if (!lc(p)) { while (p && p == lc(par[p])) p = par[p]; p = par[p]; }
        else { p = lc(p); while (p && rc(p)) p = rc(p); }
        return p;
    }
    int insert(int l, int v)
    {
        int p = find_(l + 1), q = find_(l + 2);
        splay(p, 0);
        splay(q, p);
        int r = make_node(v);
        par[r] = q; lc(q) = r;
        size[q]++, size[p]++;
        splay(r, 0);
        return r;
    }
    void remove(int p)
    {
        int lp = pre(p), rp = suc(p);
        splay(lp, 0);
        splay(rp, root);
        lc(rp) = 0;
        size[rp]--;
        size[lp]--;
        return ;
    }
    void init(void)
    {
        root = make_node(0);
        rc(root) = make_node(0);
        par[rc(root)] = root;
        size[root] = 2;
        return ;
    }
} st;

int n, m;
map<int, int> mp; // Actual ID -> node # in splay
char str[32];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    st.init();
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        mp[x] = st.insert(i - 1, x);
    }
    // Can you answer these queries (-→_-→)
    for (int idx = 1; idx <= m; idx++) {
        scanf("%s", str);
        int p, rel;
        if (str[0] == 'T') {
            scanf("%d", &p);
            int nd = mp[p];
            st.remove(nd);
            mp[p] = st.insert(0, p);
        } else if (str[0] == 'B') {
            scanf("%d", &p);
            int nd = mp[p];
            st.remove(nd);
            mp[p] = st.insert(n - 1, p);
        } else if (str[0] == 'I') {
            scanf("%d%d", &p, &rel);
            if (rel == 0) // What use of this...
                continue;
            int nd = mp[p];
            int rn = st.get_rank(nd);
            rn += rel; // New insert position
            st.remove(nd);
            mp[p] = st.insert(rn - 1, p);
        } else if (str[0] == 'A') {
            scanf("%d", &p);
            int nd = mp[p];
            int rn = st.get_rank(nd);
            printf("%d\n", rn - 1);
        } else if (str[0] == 'Q') {
            scanf("%d", &p);
            int nd = st.find(p);
            printf("%d\n", st.val[nd]);
        }
    }
    return 0;
}