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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 300100
#define ll long long
using namespace std;
int n, m, q;
#define lc T[i].ch[0]
#define rc T[i].ch[1]
struct Splay {
ll v; int ch[2], cnt, sz;
} T[maxn * 20]; int top, rt[maxn], f[maxn * 20];
inline int get(int i) { return T[f[i]].ch[1] == i; }
inline int newnode(ll v, int cnt) {
int i = ++top;
return T[i] = { v, 0, 0, cnt, cnt }, i;
}
inline void clear(int i) {
T[i] = { 0, 0, 0, 0, 0 };
f[i] = 0;
}
inline void update(int i) { T[i].sz = T[lc].sz + T[rc].sz + T[i].cnt; }
inline void rotate(int x) {
int fa = f[x], ffa = f[f[x]], wx = get(x);
f[fa] = x; f[T[x].ch[wx ^ 1]] = fa; f[x] = ffa;
if (ffa) T[ffa].ch[T[ffa].ch[1] == fa] = x;
T[fa].ch[wx] = T[x].ch[wx ^ 1]; T[x].ch[wx ^ 1] = fa;
update(fa); update(x);
}
void Splay(int &rt, int i, int k = 0) {
for (int fa = f[i]; fa != k; rotate(i), fa = f[i])
if (f[fa] != k) rotate(get(fa) == get(i) ? fa : i);
if (!k) rt = i;
}
int findk(int &rt, int k) {
int i = rt;
while (1) {
if (k <= T[lc].sz) { i = lc; continue; }
k -= T[lc].sz;
if (k <= T[i].cnt) return Splay(rt, i), i;
k -= T[i].cnt; i = rc;
}
}
void insert(int &rt, ll v, int cnt) {
int i = rt;
if (!rt) return (void) (rt = newnode(v, cnt));
while (rc) i = rc;
rc = newnode(v, cnt); f[rc] = i;
swap(T[i].v, T[rc].v); swap(T[i].cnt, T[rc].cnt);
Splay(rt, rc);
}
void del(int &rt) {
int i = T[rt].ch[0], o = rt;
while (rc) i = rc; Splay(rt, i);
T[i].ch[1] = T[o].ch[1]; f[T[o].ch[1]] = i; update(i);
clear(o);
}
ll query(int &rt, int i, int k) {
findk(rt, k + 1); int p; ll ans;
k -= T[T[rt].ch[0]].sz - 1; ans = T[rt].v + k - 1;
if (k > 1) {
p = newnode(T[rt].v, k - 1);
T[p].ch[0] = T[rt].ch[0]; f[T[rt].ch[0]] = p; update(p);
T[rt].ch[0] = p; f[p] = rt; update(rt);
}
if (k < T[rt].cnt) {
p = newnode(T[rt].v + k, T[rt].cnt - k);
T[p].ch[1] = T[rt].ch[1]; f[T[rt].ch[1]] = p; update(p);
T[rt].ch[1] = p; f[p] = rt; update(rt);
}
del(rt);
insert(rt, T[findk(::rt[0], i + 1)].v, 1);
del(::rt[0]); insert(::rt[0], ans, 1);
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> q;
for (int i = 0; i <= n; ++i) {
int l = ++top, r = ++top;
rt[i] = l; f[r] = l;
T[l] = { 0, 0, r, 1, 2 };
T[r] = { 0, 0, 0, 1, 1 };
if (i > 0) insert(rt[i], 1ll * (i - 1) * m + 1, m - 1);
}
for (int i = 1; i <= n; ++i) insert(rt[0], 1ll * i * m, 1);
for (int i = 1; i <= q; ++i) {
int x, y; cin >> x >> y;
if (y == m) {
ll ans = T[findk(rt[0], x + 1)].v;
cout << ans << "\n";
del(rt[0]); insert(rt[0], ans, 1);
}
else cout << query(rt[x], x, y) << "\n";
}
return 0;
}
|