[ 【NOIP2017 提高组】列队]（https://www.luogu.com.cn/problem/P3960）
将每一行的第1到m-1个和第m列分离出来
分析知这n+1个“区间”要维护弹出第k个和插入最后
使用平衡树,一个区间若没有被算则用[l,r]表示(方伯伯的OJ)
点击查看代码
#include <stdio.h>
#include <string.h>
const int N = 3e5 + 5;
typedef long long LL;
struct Node {
int son[2], fa;
LL l, r, size; // l,r 为区间左右端点
} tr[N * 8];
int idx, n, m, q;
void push_up(int u) {
tr[u].size = tr[tr[u].son[0]].size + tr[tr[u].son[1]].size + (tr[u].r - tr[u].l + 1);
}
void rotate(int x) {
int y = tr[x].fa, z = tr[y].fa, k = tr[y].son[1] == x;
tr[tr[z].son[tr[z].son[1] == y] = x].fa = z;
tr[tr[y].son[k] = tr[x].son[!k]].fa = y;
tr[tr[x].son[!k] = y].fa = x;
push_up(y), push_up(x);
}
struct Splay {
int root;
void splay(int x, int rt) {
static int y, z;
while(tr[x].fa != rt) {
y = tr[x].fa, z = tr[y].fa;
if(z != rt) rotate((tr[y].son[1] == x) ^ (tr[z].son[1] == y) ? x : y);
rotate(x);
}
if(!rt) root = x;
}
void init(LL l, LL r) {
root = ++ idx;
tr[idx].fa = tr[idx].son[0] = tr[idx].son[1] = 0;
tr[idx].l = l, tr[idx].r = r, tr[idx].size = r - l + 1;
}
int build(int fa, int l, int r) {
if(l > r) return 0;
int mid = (l + r) >> 1, u = ++ idx;
tr[u].fa = fa, tr[u].l = tr[u].r = LL(mid) * m;
tr[u].son[0] = build(u, l, mid - 1);
tr[u].son[1] = build(u, mid + 1, r);
push_up(u); return u;
}
// 将u的前k个保留,后面的作为返回值的新节点
int split(int u, int k) {
int v = ++ idx;
tr[v].l = tr[u].l + k, tr[v].r = tr[u].r;
tr[u].r = tr[u].l + k - 1;
// 将v节点放到u的后继节点的左儿子并旋转到根
if(tr[u].son[1]) {
int t = tr[u].son[1];
while(tr[t].son[0]) t = tr[t].son[0];
tr[tr[t].son[0] = v].fa = t;
} else tr[tr[u].son[1] = v].fa = u;
splay(v, 0);
return v;
}
LL popkth(int k) {
int u = root, lssz;
while(u) {
lssz = tr[tr[u].son[0]].size;
if(lssz >= k) u = tr[u].son[0];
else if(lssz + (tr[u].r - tr[u].l + 1) >= k) {
k -= lssz;
if(k < tr[u].r - tr[u].l + 1) split(u, k);
if(k > 1) u = split(u, k - 1);
break;
} else k -= lssz + (tr[u].r - tr[u].l + 1), u = tr[u].son[1];
}
// 现在u为这个单独的节点,将其删除
splay(u, 0);
tr[tr[u].son[0]].fa = tr[tr[u].son[1]].fa = 0;
if(tr[u].son[0]) {
int t = tr[u].son[0];
while(tr[t].son[1]) t = tr[t].son[1];
splay(t, 0);
tr[tr[t].son[1] = tr[u].son[1]].fa = t;
push_up(t);
} else root = tr[u].son[1];
return tr[u].l;
}
void push(LL val) {
int u = root, fu = 0;
while(u) fu = u, u = tr[u].son[1];
u = ++ idx, tr[u].l = tr[u].r = val, tr[u].fa = fu, tr[u].size = 1;
if(fu) tr[fu].son[1] = u;
splay(u, 0);
}
} tree[N];
int main() {
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i ++) tree[i].init(m * LL(i - 1) + 1, m * LL(i) - 1);
tree[0].root = tree[0].build(0, 1, n);
LL tmp; // 答案
for(int i = 1, x, y; i <= q; i ++) {
scanf("%d%d", &x, &y);
tree[x].push(tree[0].popkth(x));
printf("%lld\n", tmp = tree[x].popkth(y));
tree[0].push(tmp);
}
return 0;
}
</details>