题目大意：给定一个 $n \times m$ 的方阵，初始时第 $i$ 行第 $j$ 列的人的编号为 $(i-1) \times m + j$，$q$ 次给出 $x,y$，让第 $x$ 行 $y$ 列的人出队，然后其他人先向左看齐，后向前看齐，再把出队的人放在第 $n$ 行 $m$ 列，请你输出每次出队的人的编号。$n,m,q \leq 3 \times 10^5$
对于 $n,m \leq 50000, q \leq 500$ 的数据，可以离散化，但是不能用 map，因为 map 的所有操作都是带 log 的。
考虑 $q \leq 500$，即最多涉及到 $500$ 个行，于是可以将行离散化，开一个 $500 \times 50000$ 的数组，最后一列单独开一个 $50000 \times 1$ 的数组。
对于所有 $x=1$ 的数据，可以用 treap，注意在 maintain 函数中所加的是 $1$ 而不是 $num[cur]$ 时，一定要加上 $cur \neq 0$ 的判断。
（顺便提一下线段树做法：用 $0,1$ 表示该位置有没有人，初始时 $1 \cdots n+m-1$ 的位置都是 $1$，每删一个元素就把它变成 $0$，把它新插入的位置变成 $1$，查询第 $i$ 个元素就是查询前缀和等于 $i$ 的位置）
#include <cstdio>
#include <cstdlib>
const int N = 1000000;
typedef long long LL;
int siz[N], rnd[N], ch[N][2], root, cnt; LL id[N], ans;
int read() {
int x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x;
}
void newNode(int &cur, LL x) {
cur = ++cnt, id[cur] = x;
siz[cur] = 1, rnd[cur] = rand();
}
void maintain(int cur) {
if (cur) siz[cur] = siz[ch[cur][0]] + siz[ch[cur][1]] + 1; //一定要加if(cur)的判断
}
void rotate(int &cur, int k) {
int fa = ch[cur][k^1];
ch[cur][k^1] = ch[fa][k], ch[fa][k] = cur;
maintain(cur), maintain(fa), cur = fa;
}
void insert(int &cur, LL x) {
if (!cur) newNode(cur, x);
else {
insert(ch[cur][1], x);
if (rnd[ch[cur][1]] > rnd[cur]) rotate(cur, 0);
maintain(cur);
}
}
void del(int &cur) {
if (!ch[cur][0]) cur = ch[cur][1];
else if (!ch[cur][1]) cur = ch[cur][0];
else {
int k = rnd[ch[cur][0]] > rnd[ch[cur][1]] ? 0 : 1;
rotate(cur, k), del(ch[cur][k]), maintain(cur);
}
}
void kth(int &cur, int k) { //查找第k个元素并删除
if (!cur) return;
if (siz[ch[cur][0]] == k - 1) ans = id[cur], del(cur);
else if (siz[ch[cur][0]] >= k) kth(ch[cur][0], k);
else kth(ch[cur][1], k - siz[ch[cur][0]] - 1);
maintain(cur);
}
int main() {
int n = read(), m = read(), T = read();
for (int i = 1; i <= m; ++i) insert(root, i);
for (int i = 2; i <= n; ++i) insert(root, 1LL * i * m);
while (T--) {
int x = read(), y = read();
kth(root, y);
printf("%lld\n", ans);
insert(root, ans);
}
return 0;
}
平衡树
对于 $n,m,q \leq 3 \times 10^5$ 的数据，可以每一行都开一个 treap，最后一列单独开一个 treap，treap 中每个节点是一段连续的区间，且区间内的元素编号是一个等差数列，维护每个区间的第一个元素编号以及区间的大小，每次用插入操作模拟区间分裂即可。
#include <cstdio>
#include <cstdlib>
typedef long long LL;
const int N = 1500005, M = 300005;
int siz[N], num[N], rnd[N], ch[N][2], root[M], cnt; LL id[N], ans;
int read() {
int x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x;
}
void newNode(int &cur, LL x, int y) {
cur = ++cnt;
siz[cur] = num[cur] = y;
id[cur] = x, rnd[cur] = rand();
}
void maintain(int cur) {
siz[cur] = num[cur] + siz[ch[cur][0]] + siz[ch[cur][1]];
}
void rotate(int &cur, int k) {
int fa = ch[cur][k^1];
ch[cur][k^1] = ch[fa][k], ch[fa][k] = cur;
maintain(cur), maintain(fa), cur = fa;
}
void insert(int &cur, LL x, int y, int k) { //x表示块首元素的编号, y表示块的大小, k表示插入队首/队尾
if (!cur) newNode(cur, x, y);
else {
insert(ch[cur][k], x, y, k);
if (rnd[ch[cur][k]] > rnd[cur]) rotate(cur, k ^ 1);
maintain(cur);
}
}
void kth(int &cur, int k, int d) { //d表示公差
if (siz[ch[cur][0]] + 1 <= k && k <= siz[ch[cur][0]] + num[cur]) {
ans = id[cur] + 1LL * (k - siz[ch[cur][0]] - 1) * d;
if (ans == id[cur]) { //删除的是块首
id[cur] += d, --num[cur];
} else {
if (siz[ch[cur][0]] + num[cur] > k) //删除的不是块尾
insert(ch[cur][1], ans + d, siz[ch[cur][0]] + num[cur] - k, 0);
num[cur] = k - siz[ch[cur][0]] - 1;
}
} else if (siz[ch[cur][0]] >= k) {
kth(ch[cur][0], k, d);
} else {
kth(ch[cur][1], k - siz[ch[cur][0]] - num[cur], d);
}
maintain(cur);
}
int main() {
int n = read(), m = read(), q = read();
for (int i = 1; i <= n; ++i) insert(root[i], 1LL * (i - 1) * m + 1, m - 1, 1);
insert(root[n+1], m, n, 1);
while (q--) {
int x = read(), y = read();
if (y < m) {
kth(root[x], y, 1);
insert(root[n+1], ans, 1, 1);
printf("%lld\n", ans);
kth(root[n+1], x, m);
insert(root[x], ans, 1, 1);
} else {
kth(root[n+1], x, m);
insert(root[n+1], ans, 1, 1);
printf("%lld\n", ans);
}
}
return 0;
}
时间复杂度 $O(q \log m)$
线段树
这个做法非常神仙……
比如一个 $3 \times 5$ 的矩阵，我们有这样 $4$ 组询问：
1 3
1 2
3 1
1 4
用 $4$ 表示最后一列，那么所有的出队情况如下：
1 3
4 1
1 2
4 1
3 1
4 3
1 4
4 1
然后把它们分为三组：
1 3
1 2
1 4
3 1
4 1
4 1
4 3
4 1
用一棵线段树分别计算每行第 $i$ 个出队的人的位置，用 $1 \cdots m-1$ 表示初始时的位置，$m \cdots q$ 表示后来插入的位置，每走一个人就把他的位置变成 $0$，每次查询前缀和为 $i$ 的位置。如图以第一行为例：
其他行和最后一列也同理，都是用同一棵线段树来操作，但是不需要每次都 $memset$，只需要把上一次操作减去的值再加回来即可，因为是一共有 $q$ 次操作，所以最多加 $q$ 次。以下是每行每次出队的元素的位置：
3 (1)
2 (1)
6 (1)
1 (3)
1 (4)
2 (4)
5 (4)
3 (4)
将它们按照询问顺序排序：
3 (1)
1 (4)
2 (1)
2 (4)
1 (3)
5 (4)
6 (1)
3 (4)
对于每一行，我们开一个 $vector$ 储存后加入的元素（当然用邻接表更好），具体的操作如下：
- 对于第 $i$ 行，如果当前出队的元素位置 $j$ $<m$，则直接输出 $(i-1)m+j$，否则输出当前行的 $vector$ 中第 $j-m+1$ 个元素
- 输出完后，将该元素 $push\text{_}back$ 到对应行(列)的 $vector$ 中
时间复杂度 $O(q\log(q+m))$