Luogu P3960 [NOIP 2017] 列队

qwq

我菜,BIT不会做。

每次我们要从列队中抽出(x, y)放到(n, m),很容易就能想到在每一行开一棵平衡树来维护每一行的情况(逃

$N * M \le 9 \times 10 ^ {10}$,每个同学开个点空间不可承受。可以按区间开点,复杂度就可以接受了。用非旋Treap比较好做。

给每一行开[1, m - 1]的平衡树,对于最后一列我们要单独开,因为向左看齐时最后一列的变动是特殊的。因此同学出列时就有了在第m列和不在第m列两种情况。

同学出列时在第m列的情况比较简单,直接把平衡树split成 a [1, x - 1], b [x, x], c [x + 1, n],先 merge a c,再merge a b,就达成了把这位同学安排到(n, m)的目的。

同学出列时不在第m列就比较谔谔了。先把x行的平衡树split成 a [1, y - 1], b [y, y], c [y + 1, n - 1],再把m列的平衡树split成 u [1, y - 1], v [y, y], w [y + 1, n]。merge c v, merge a c, 完成向左看齐。merge w b, merge u w, 完成向前看齐并归队。

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
#include <bits/stdc++.h>

const int N = 500000 + 233;
int n, m, q;

inline int read() {
int a = 0;
char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
return a;
}

namespace BST {
int tot, root[N], ch[N << 5][2];
long long key[N << 5], l[N << 5], r[N << 5], siz[N << 5];

inline int newNode(long long p, long long q) {
key[++tot] = rand(), l[tot] = p, r[tot] = q, siz[tot] = q - p + 1;
return tot;
}

inline void update(int p) {
siz[p] = siz[ch[p][0]] + siz[ch[p][1]] + r[p] - l[p] + 1;
}

void merge(int &p, int x, int y) {
if (!x || !y) return (void)(p = x + y);
if (key[x] < key[y])
p = x, merge(ch[p][1], ch[x][1], y);
else
p = y, merge(ch[p][0], x, ch[y][0]);
update(p);
}

void cut(int p, int k) {
if (k >= r[p] - l[p] + 1) return;
int x = newNode(l[p] + k, r[p]);
r[p] = l[p] + k - 1;
merge(ch[p][1], x, ch[p][1]);
update(p);
}

void split(int p, int &x, int &y, int k) {
if (!p) return (void)(x = y = 0);
if (siz[ch[p][0]] >= k) {
y = p;
split(ch[p][0], x, ch[y][0], k);
} else {
x = p;
cut(p, k - siz[ch[p][0]]);
x = p;
split(ch[p][1], ch[x][1], y, k - siz[ch[p][0]] - (r[p] - l[p] + 1));
}
update(p);
}
} // namespace BST

signed main() {
using namespace BST;
srand(clock() + rand() + time(0));
n = read(), m = read(), q = read();
for (int i = 1; i <= n; ++i)
root[i] = newNode((long long)(i - 1) * m + 1, (long long)i * m - 1);
for (int i = 1; i <= n; ++i)
merge(root[n + 1], root[n + 1],
newNode((long long)i * m, (long long)i * m));
for (int i = 1; i <= q; ++i) {
int x = read(), y = read();
if (y != m) {
int a, b, c;
split(root[x], a, b, y), split(a, a, c, y - 1);
printf("%lld\n", l[c]);
int u, v, w;
split(root[n + 1], u, v, x), split(u, u, w, x - 1);
merge(b, b, w), merge(root[x], a, b);
merge(v, v, c), merge(root[n + 1], u, v);
} else {
int a, b, c;
split(root[n + 1], a, b, x), split(a, a, c, x - 1);
printf("%lld\n", l[c]);
merge(b, b, c), merge(root[n + 1], a, b);
}
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×