本题的 $n$ 特别大,如果直接开那么大的空间,想必会直接超时。所以我们可以先把所有“用户”合并成一个点,需要访问到哪个就进行分裂。这样的话 $m$ 次操作每次都只会分裂一次,时间复杂度就能保证在 $O(m\log m)$ ,空间也不会炸。

另外本题只有提到最前面和提到最后面两种操作,使用平衡树的必要不大,用动态开点线段树就好了。

p.s. 感觉 Leafy Tree 和这个好像啊 (=’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
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
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 100010;
int n, m, x, y, k, u, cnt, opt, tmp, last, left_side, right_side;
std::map < int, int > mp;

struct node {
int value, size;
node *l, *r;
node() {
value = size = 0;
l = r = NULL;
}
node (int a, int b, node *c, node *d) {
value = a, size = b;
l = c, r = d;
}
} *root, *null, *st[maxn << 6], t[maxn << 6];

int get_size(int l, int r) {
return std::max(std::min(r, n) - std::max(1, l) + 1, 0);
}

node *newnode(int l, int r) {
cnt++;
if (l == r) t[cnt] = node(l, (1 <= l && l <= n ? 1 : 0), null, null);
else t[cnt] = node(0, get_size(l, r), null, null);
return st[cnt] = &t[cnt];
}

int query(int k, int l, int r, node *&u) {
if (u == null) u = newnode(l, r);
if (l == r) return u->value;
int mid = (l + r) >> 1;
int left_size = (u->l == null) ? get_size(l, mid) : u->l->size;
if (k <= left_size) return query(k, l, mid, u->l);
return query(k - left_size, mid + 1, r, u->r);
}

int rank(int x, int l, int r, node *&u) {
if (u == null) u = newnode(l, r);
if (l == r) return 1;
int mid = (l + r) >> 1;
if (x <= mid) return rank(x, l, mid, u->l);
return rank(x, mid + 1, r, u->r) + ((u->l == null) ? get_size(l, mid) : u->l->size);
}

void modify(int x, int y, int l, int r, node *&u) {
if (u == null) u = newnode(l, r);
if (l == r) { u->value = y; return; }
int mid = (l + r) >> 1;
if (x <= mid) modify(x, y, l, mid, u->l);
else modify(x, y, mid + 1, r, u->r);
}

void update(int x, int y, int z, int l, int r, node *&u) {
if (u == null) u = newnode(l, r);
u->size += y;
if (l == r) { u->value = z; return; }
int mid = (l + r) >> 1;
if (x <= mid) update(x, y, z, l, mid, u->l);
else update(x, y, z, mid + 1, r, u->r);
}

int main() {

n = read(), m = read();
for (int i = 0; i < (maxn << 6); i++)
st[i] = &t[i];
null = new node(0, 0, null, null);
root = new node(0, n, null, null);
left_side = 1, right_side = n;

for (int i = 1; i <= m; i++) {
opt = read();
if (opt == 1) {
x = read() - last, y = read() - last;
k = mp.find(x) != mp.end() ? mp[x] : x;
printf("%d\n", last = rank(k, -m, n + m, root));
modify(k, y, -m, n + m, root);
mp.erase(x), mp[y] = k;
} else if (opt == 2) {
x = read() - last, k = mp.find(x) != mp.end() ? mp[x] : x;
printf("%d\n", last = rank(k, -m, n + m, root));
update(k, -1, -1, -m, n + m, root);
update(mp[x] = --left_side, 1, x, -m, n + m, root);
} else if (opt == 3) {
x = read() - last, k = mp.find(x) != mp.end() ? mp[x] : x;
printf("%d\n", last = rank(k, -m, n + m, root));
update(k, -1, -1, -m, n + m, root);
update(mp[x] = ++right_side, 1, x, -m, n + m, root);
} else if (opt == 4) {
k = read() - last;
printf("%d\n", last = query(k, -m, n + m, root));
}
}

return 0;
}