Skip to content

「ZJOI2006」书架

题解约 1.7 千字
# 洛谷 # 2006 # 数据结构 # 平衡树 # Treap # ZJOI
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

小 T 有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用 11 到 nn 的正整数给每本书都编了号。

小 T 在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小 T 的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有 xx 本书，那么放回去时这本书上面就只可能有 x−1x - 1、xx 或 x+1x + 1 本书。

当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小 T 会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。

久而久之，小 T 的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：

  • 编号为 xx 的书在书柜的什么位置。
  • 从上到下第 ii 本书的编号是多少。

#输入格式

第一行有两个整数，分别表示书的个数 nn 以及命令条数 mm。

第二行有 nn 个整数，第 ii 个整数表示初始时从上向下书第 ii 本书的编号 pip_i。

接下来 mm 行，每行表示一个操作。每行初始时有一个字符串 opop。

  • 若 opop 为 Top，则后有一个整数 ss，表示把编号为 ss 的书放在最上面。
  • 若 opop 为 Bottom，则后有一个整数 ss，表示把编号为 ss 的书放在最下面。
  • 若 opop 为 Insert，则后有两个整数 s,ts, t，表示若编号为 ss 的书上面有 xx 本书，则放回这本书时他的上面有 x+tx + t 本书。
  • 若 opop 为 Ask，则后面有一个整数 ss，表示询问编号为 ss 的书上面有几本书。
  • 若 opop 为 Query，则后面有一个整数 ss，询问从上面起第 ss 本书的编号。

#输出格式

对于每次查询，输出一行一个整数表示答案。

#输入输出样例

样例输入 #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%100\% 的数据，保证：

  • 3≤n,m≤8×1043 \leq n, m \leq 8 \times 10^4；
  • pip_i 是一个 1∼n1 \sim n 的排列；
  • 1≤s≤n1 \leq s \leq n，−1≤t≤1-1 \leq t \leq 1，opop 只可能是输入的五种字符串之一；
  • 当编号为 ss 的书上面没有书的时候，不会对它进行 Insert s -1 操作；
  • 当编号为 ss 的书下面没有书的时候，不会对它进行 Insert s 1 操作。

#思路

本题可以使用 FHQ Treap 解决。

设 pxp_x 记录编号为 xx 的书对应的节点，方便后续操作。

执行 Top 操作时将整棵树分裂成三份 —— ss 之前的书，ss 本身，ss 之后的书。然后将其重拍顺序合并。Bottom 操作同理。

对于 Insert 操作，有三种情况：

  1. 当 t=0t = 0 时，无需进行任何操作；
  2. 当 t<0t < 0 时，将 ss 插入到 ss 前的第 −t-t 个位置；
  3. 当 t>0t > 0 时，将 ss 插入到 ss 后的第 tt 个位置。

对于 Ask 操作直接输出 ss 在树上的排名即可。

对于 Query 操作，在树上执行分裂，将第 ss 本书取出来记录编号再合并即可。

#代码

C++
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include <iostream>
#include <cstdlib>
#include <string>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 8e4 + 5;

struct node {
    node *lchild, *rchild, *fa;
    std::size_t size;
    int value, key;

    node()
        : lchild(nullptr), rchild(nullptr), fa(nullptr), size(0), value(0), key(rand()) {}

    node(int _value)
        : lchild(nullptr), rchild(nullptr), fa(nullptr), size(1), value(_value), key(rand()) {}

    ~node() {
        if (lchild != nullptr) delete lchild;
        if (rchild != nullptr) delete rchild;
    }

    inline std::size_t lsize() {
        return lchild == nullptr ? 0 : lchild->size;
    }

    inline std::size_t rsize() {
        return rchild == nullptr ? 0 : rchild->size;
    }

    inline void pushup() {
        size = 1;

        if (lchild != nullptr) {
            size += lchild->size;
            lchild->fa = this;
        }

        if (rchild != nullptr) {
            size += rchild->size;
            rchild->fa = this;
        }
    }

    inline std::size_t pos() {
        std::size_t ret = lsize() + 1;
        node *cur = this;

        while (cur->fa != nullptr) {
            if (cur->fa->rchild == cur) {
                ret += cur->fa->lsize() + 1;
            }

            cur = cur->fa;
        }

        return ret;
    }
};

int n, m;
node *root, *p[N];

std::pair<node *, node *> split(node *u, int k) {
    if (u == nullptr) return std::make_pair(nullptr, nullptr);

    if (k <= u->lsize()) {
        auto o = split(u->lchild, k);

        u->lchild = o.second;
        u->pushup();
        o.second = u;

        return o;
    }

    auto o = split(u->rchild, k - u->lsize() - 1);

    u->rchild = o.first;
    u->pushup();
    o.first = u;

    return o;
}

template <typename... Args>
node *merge(node *x, Args... args) {
    return merge(x, merge(args...));
}

template <>
node *merge(node *x, node *y) {
    if (x == nullptr) return y;
    if (y == nullptr) return x;

    if (x->key < y->key) {
        x->rchild = merge(x->rchild, y);
        x->pushup();

        return x;
    }

    y->lchild = merge(x, y->lchild);
    y->pushup();

    return y;
}

inline void top(const int &x) {
    int k = p[x]->pos();

    auto p = split(root, k - 1);
    auto q = split(p.second, 1);

    root = merge(q.first, p.first, q.second);
}

inline void bottom(const int &x) {
    int k = p[x]->pos();

    auto p = split(root, k - 1);
    auto q = split(p.second, 1);

    root = merge(p.first, q.second, q.first);
}

inline void insert(const int &x, const int &y) {
    if (!y) return;

    int k = p[x]->pos();
    auto p = split(root, k - 1);
    auto q = split(p.second, 1);

    if (y > 0) {
        auto t = split(q.second, y);
        root = merge(p.first, t.first, q.first, t.second);
    } else {  // y < 0
        auto t = split(p.first, k + y - 1);
        root = merge(t.first, q.first, t.second, q.second);
    }
}

inline int ask(const int &x) {
    return p[x]->pos() - 1;
}

inline int query(const int &x) {
    auto p = split(root, x - 1);
    auto q = split(p.second, 1);

    int res = q.first->value;

    root = merge(p.first, q.first, q.second);

    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1, x; i <= n; i++) {
        cin >> x;

        root = merge(root, p[x] = new node(x));
    }

    while (m--) {
        std::string op;
        int s, t;

        cin >> op >> s;

        switch (op[0]) {
            case 'T': {  // op == "Top"
                top(s);

                break;
            }
            case 'B': {  // op == "Bottom"
                bottom(s);

                break;
            }
            case 'I': {  // op == "Insert"
                cin >> t;

                insert(s, t);

                break;
            }
            case 'A': {  // op == "Ask"
                cout << ask(s) << endl;

                break;
            }
            case 'Q': {  // op == "Query"
                cout << query(s) << endl;

                break;
            }
        }
    }

    // Cleanup
    delete root;

    return 0;
}