P3960 [NOIP 2017 提高组] 列队题解
大致思路：
方法1：
首先，问题分成两个操作。
-
向左看齐（行内的单点查找和删除）。
-
向前看齐（最后一列的单点查找和删除）。
我们把图分成两个部分：
-
n\times(m-1) 的左侧矩形。
-
最右侧的 n 这一列。
考虑最后一列有 n+q 个位置。第 n+i 个位置表示在第 i 次列队中出队的人的编号，放在最下面（可以凭空想一下）。我们不妨先进行向前看齐，找到并删除最后一列第 x 大的位置。现在我们得到一个编号。代表这次看齐中最后一列的第 x 个位置要被挪走了。
之后首先判断要移走的列是不是最后一列，如果是，则这次列队中出队的人的编号，就已经找到了（也就是最后一列找到的位置的编号），把 id_{n+i} 置为 id_{find} 就行。否则第 x 行最后插入这个被去掉的元素 id_{find}。然后找第 x 行的第 y 大位置，并删除他。如果这个位置小于 m，则显然是原来的编号，直接计算就行。
如果等于 m，则这一行显然被操作过，否则要移走的列，就是最后一列了。而在移走的时候这一行最后的元素，已经被放在了末尾。于是这个时候，只需要找到之前添加的对应位置的数（在 m-1 的分割外面的）。他的编号就是这个询问的答案，之后再把他放到最后一列末尾就行了！
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 6e6 + 20;
int n, m, q, cnt, rt[N / 2];
struct node
{
int s, ls, rs;
} t[N]; // 可持久化线段树节点
LL ID[N], pos;
vector<LL> G[N / 2]; // 每行末尾的新编号
#define mid (l + r >> 1)
#define ls t[p].ls
#define rs t[p].rs
#define lson ls, l, mid
#define rson rs, mid + 1, r
int F(int k, int &p, int l, int r)
{ // 去掉第k大（初始时每个区间都是全部点都在）
if (!p)
t[p = ++cnt].s = r - l + 1; // 新建一个点，长度是全部
--t[p].s; // 每次减少1（第k大在这个区间里，把他移走等效于区间长度减少1）
if (l == r)
return l; // 找到点了（这也是第k大），返回下标
int sl = ls ? t[ls].s : mid - l + 1; // 如果左子树存在，就取左子树里剩余的，否则剩余的视为全部长度
if (sl >= k)
return F(k, lson); // 线段树上二分，看第k大在哪颗子树，就移走他
return F(k - sl, rson);
}
// ID_i: 最后一列第 i 个位置的编号
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i)
ID[i] = 1ll * i * m;
for (int i = 1; i <= q; ++i)
{
int x, y;
cin >> x >> y;
int kk = F(x, rt[0], 1, n + q); // 倒着考虑，先最后一列上下对齐。找到并去掉最后一列的第x大
// 找行，一共最多 n+q 行，找当前图里的第 x 行（之前如果已经取了x或以下的，这时候找到的行就不一样了）
if (y == m)
ID[n + i] = ID[kk]; // 如果移走的元素是第m列，就不用左右对齐了。
else
{
G[x].push_back(ID[kk]); // 把填进去的元素放在 x 行末尾
pos = F(y, rt[x], 1, m + q); // 考虑前面的操作。第 x 行左右对齐，去掉第 y 个
if (pos < m)
ID[n + i] = 1ll * (x - 1) * m + pos; // 如果位置在原图里，且不是最后一个，直接算出位置，变成最后一列最下面的一个位置
// 如果恰好是最后一个位置m，肯定不是第一次操作这行。之前操作过一次G[x]已经有最后一个了
else
ID[n + i] = G[x][pos - m]; // 否则新的行最后一共元素就是第x行从前往后加入的
}
cout << ID[n + i] << '\n';
}
}
方法2：
显然可以使用平衡树，我们需要维护两种操作：
操作 1：维护每一行。
操作 2：维护每一列。
因为我们不可能对于每个点暴力使用平衡树，不然你就需要看 9 \times 10^{10}。
然后我们考虑如何维护每一行，我们会发现 (x, y) 是不是相对于行就是在第 x 行中删了第 y 个数，相当于我们对于每一行开一个平衡树。那么如何考虑列呢？首先我们会发现如果要调整列必定是在第 m 列，相当于我们只需要维护第 m 列，相当于只要给他开个平衡树，删除其中第 x 个数，然后把前面原本的 (x, y) 插入末尾。注意了使原本变化前的 (x, y)。那么题目变为有 n + 1 棵平衡树，请你维护其中一颗平衡树删除第 x 个数，或者维护第 m 列的那颗平衡树在末尾插入一个数，这样就变成模板题了，但注意到一个细节有一些数字一直连接在一起，并没有分离，那么对于我们维护平衡树，每个节点可以存一个区间，当两个数分离时，对它们进行分裂即可。