NOIP 2017 列队(Splay)

发表于 更新于 分类于

题目

题目描述

Sylvia 是一个热爱学习的女孩子。

前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。

Sylvia 所在的方阵中有n*m名学生，方阵的行数为n，列数为m。

为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中的学生从1到n*m编上了号码（参见后面的样例）。即：初始时，第i行第j列 的学生的编号是(i - 1) * m + j。

然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天 中，一共发生了q件这样的离队事件。每一次离队事件可以用数对(x, y) (1<=x<=n, 1<=y<=m)描述，表示第x行第y列的学生离队。

在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达这样的两条指令：

向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条指令之后，空位在第x行第m列。

向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条指令之后，空位在第n行第m列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后，下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第n行 第m列一个空位，这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学的编号是多少。

注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后方阵中同学的编号可能是乱序的。

输入输出格式

输入格式：

输入共q+1行。

第1行包含3个用空格分隔的正整数n,m,q，表示方阵大小是n行m列，一共发生了`q次事件。

接下来q行按照事件发生顺序描述了q件事件。每一行是两个整数x,y，用一个空格分隔，表示这个离队事件中离队的学生当时排在第x行第y列。

输出格式：

按照事件输入的顺序，每一个事件输出一行一个整数，表示这个离队事件中离队学生的编号。

输入输出样例

输入样例：

1
2
3
4
2 2 3 
1 1 
2 2 
1 2

输出样例：

1
2
3
1
1
4

题解

这道题我用splay做

观察到每次操作的时候，队列的变化是先向左，然后最后一列向上

我们考虑，每一行用一颗splay来维护，而最后一列单独用一棵splay来维护

每次操作就可以暴力模拟了

但是这样很可能会MLE

解决方案:

观察到最初每一行编号是连续的，那么splay中每一个结点作为一个区间，

需要单独用一个结点的时候就将区间分割

代码 Code

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
216
217
218
219
220
221
222
223
224
225
226
227
228
#include<cstdio>
using namespace std;
long long f(-1);
inline char GetCharacter() {
	static char buf[2000000], *p1 = buf, *p2 = buf;
	return (p1 == p2) &&
	       (p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ? 
	       EOF : *p1++;
}
#define IS_DIGIT(c) (c >= '0' && c <= '9')
inline void Read(long long &x) {
	f = 1, x = 0;
	static char c = GetCharacter();
	while (!IS_DIGIT(c)) {
		if (c == '-') f = -1;
		c = GetCharacter();
	}
	while (IS_DIGIT(c)) x = x * 10 + c - '0', c = GetCharacter();
	x *= f;
}
#undef IS_DIGIT
struct node {
    long long l, r, size;
    node *left, *right, *father;
    node(const long long &le, const long long &ri) {
        l = le, r = ri, size = r - l + 1;
        left = right = father = NULL;
    }
};
class splay_tree {
    public:
        node *root;
    private:
        inline void update(register node *x) {
            if (x) x->size = (x->left ? x->left->size : 0) + 
                             (x->right ? x->right->size : 0) + 
                             x->r - x->l + 1ll;
        }
        inline void left_rotate(register node *x) {
            register node *y = x->father;
            y->right = x->left;
            if (x->left) x->left->father = y;
            x->father = y->father;
            if (y->father) {
                if (y == y->father->left) y->father->left = x;
                else y->father->right = x;
            }
            x->left = y;
            y->father = x;
            update(y), update(x);
        }
        inline void right_rotate(register node *x) {
            register node *y = x->father;
            y->left = x->right;
            if (x->right) x->right->father = y;
            x->father = y->father;
            if (y->father) {
                if (y == y->father->right) y->father->right = x;
                else y->father->left = x;
            }
            x->right = y;
            y->father = x;
            update(y), update(x);
        }
        inline void splay(register node *x, const node *target=NULL) {
            register node *y;
            while (x->father != target) {
                y = x->father;
                if (x == y->left) {
                    if (y->father != target && y == y->father->left) 
                      right_rotate(y);
                    right_rotate(x);
                } else {
                    if (y->father != target && y == y->father->right) 
                      left_rotate(y);
                    left_rotate(x);
                }
            }
            if (!target) root = x;
        }
        inline node *split(register node *x,const long long &rnk) {
            if (1ll < rnk && x->r - x->l + 1ll > rnk) {
                register node *y = new node(x->l + rnk - 1ll, 
                                            x->l + rnk - 1ll), 
                              *z = new node(x->l + rnk, x->r);
                x->r = x->l + rnk - 2ll, x->size = x->r - x->l + 1ll;
                z->right = x->right;
                if (x->right) x->right->father = z;
                x->right = NULL;
                y->father = x->father;
                if (x->father) {
                    if (x == x->father->right) x->father->right = y;
                    else x->father->left = y;
                } else root = y;
                y->left = x, y->right = z;
                x->father = z->father = y;
                update(x), update(z), update(y);
                return y;
            } else if (x->l == x->r) {
                return x;
            } else if (rnk == 1ll) {
                register node *y = new node(x->l, x->l);
                ++x->l, --x->size;
                y->father = x->father;
                if (x->father) {
                    if (x == x->father->left) x->father->left = y;
                    else x->father->right = y;
                } else root = y;
                y->left = x->left;
                if (x->left) x->left->father = y;
                x->left = NULL;
                x->father = y, y->right = x;
                update(x), update(y);
                return y;
            } else {
                register node *y = new node(x->r, x->r);
                --x->r, --x->size;
                y->father = x->father;
                if (x->father) {
                    if (x == x->father->right) x->father->right = y;
                    else x->father->left = y;
                } else root = y;
                y->right = x->right;
                if (x->right) x->right->father = y;
                x->right = NULL;
                x->father = y, y->left = x;
                update(x), update(y);
                return y;
            }
        }
        inline node *erase(register node *x) {
            splay(x);
            if (!x->left && !x->right) {
                root = NULL;
                return x;
            } else if (!x->right) {
                root = x->left;
                root->father = NULL;
                x->left = NULL;
                x->size = x->r - x->l + 1;
                return x;
            } else if (!x->left) {
                root = x->right;
                root->father = NULL;
                x->right = NULL;
                x->size = x->r - x->l + 1;
                return x;
            } else {
                register node *y = x->right;
                while (y->left) y = y->left;
                splay(y, x);
                y->left = x->left;
                x->left->father = y;
                root = y, y->father = x->left = x->right = NULL;
                update(root);
                x->size = x->r - x->l + 1;
                return x;
            }
        }
    public:
        splay_tree() {
            root = NULL;
        }
        inline void push_back(const long long &l, const long long &r) {
            register node *x = root;
            if (!x) {
                root = new node(l,r);
            } else {
                while (x->right) x = x->right;
                splay(x);
                x->right = new node(l, r);
                x->right->father = x;
                update(x);
            }
        }
        inline void push_back(register node *x) {
            register node *y = root, *z = NULL;
            while (y) {
                z = y;
                y = y->right;
            }
            if (z) {
                splay(z);
                z->right = x, x->father = z;
                update(z);
            } else {
                root = x;
            }
        }
        inline node *pop(long long rnk) {
            register node *x = root;
            while (1) {
                if (x->left) {
                    if (x->left->size >= rnk) x = x->left;
                    else {
                        rnk -= x->left->size;
                        if (x->r - x->l + 1 >= rnk) break;
                        else rnk -= x->r - x->l + 1, x = x->right;
                    }
                } else {
                    if (x->r - x->l + 1 >= rnk) break;
                    else rnk -= x->r - x->l + 1, x = x->right;
                }
            }
            return erase(split(x, rnk));
        }
};
long long n, m, q, t1, t2;
splay_tree S[300010];
int main(int argc, char **argv) {
    Read(n), Read(m), Read(q);
    for (register int i(1); i <= n; ++i) 
      S[i].push_back(1ll + (i - 1ll) * m, i * m - 1);
    for (register int i(1); i <= n; ++i) S[0].push_back(i * m, i * m);
    while (q--) {
        Read(t1), Read(t2);
        if (t2 == m) {
            register node *x = S[0].pop(t1);
            printf("%lld\n", x->l);
            S[0].push_back(x);
        } else {
            register node *x = S[t1].pop(t2);
            printf("%lld\n", x->l);
            S[t1].push_back(S[0].pop(t1)), S[0].push_back(x);
        }
    }
    return 0;
}