考虑转化题意：
设这次操作删掉点((x, y))
对于每一次向左看齐：在第x行删除((x, y))，并将y以后的点全部前移一位
对于每一次向前看齐：x以后的点全部上移一位，并在最后一列插入((x, y))
这些操作都可以用(Splay)解决：
我们开(N+1)棵(Splay)，1到N棵表示的是第i行，[1,m-1]的位置，第(N+1)棵表示最后一列的位置
这样我们可以把所有的点都扔进一棵(Splay)里面
题意有一次转化成：
设这次操作删掉点((x, y))
对于每一次向左看齐：在第x棵(Splay)删除排名为(y)的节点，再将N+1棵(Splay)内的排名为(x)的节点删除并插入到第x棵(Splay)中
对于每一次向前看齐：在第(N+1)棵(Splay)中插入((x, y))
但是这样的空间复杂度开销很大（(NM)），显然不能过这道题
发现询问次数不多，而每一次询问需要动的点也很少，所以每一棵(Splay)里面存的节点变成了一个区间
每一次删除把区间分成3份：l ~ pos - 1, pos ~ pos, pos + 1 ~ r
删掉中间一份即可
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define debug printf("Now is Line : %d
",__LINE__)
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define LL long long
il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define maxn 10000005
namespace splay {
int fa[maxn], ch[2][maxn], rt[maxn], tot;
#define pushup(x) size[x] = size[ch[0][x]] + size[ch[1][x]] + val[x].size
#define get_fa(x) (ch[1][fa[x]] == x)
LL size[maxn];
struct node {
LL l, r, size;
}val[maxn];
il void rotate(int x) {
int y = fa[x], z = fa[y], w = get_fa(x), k = get_fa(y);
ch[k][z] = x, fa[x] = z, ch[w][y] = ch[w ^ 1][x];
fa[ch[w ^ 1][x]] = y, ch[w ^ 1][x] = y, fa[y] = x;
pushup(y), pushup(x);
}
il void Splay(int k, int x, int want) {
while(fa[x] != want) {
int y = fa[x];
if(fa[y] != want) rotate(get_fa(x) == get_fa(y) ? y : x);
rotate(x);
}
if(!want) rt[k] = x;
}
il void insert(int k, LL x) {
int u = rt[k], f = 0;
while(u) f = u, u = ch[1][u];
u = ++ tot;
size[u] = 1, fa[u] = f, val[u] = (node){x, x, 1}, ch[1][f] = u, Splay(k, u, 0);
}
il LL spilt(int p, int k, LL x) {
LL s = val[k].l, t = val[k].r;
if(s != x && t != x) {
if(s + 1 < t) {
int u = ++ tot;
val[u].l = x + 1, val[u].r = val[k].r, val[u].size = (val[u].r - val[u].l + 1);
val[k].r = x - 1, val[k].size = (val[k].r - val[k].l + 1);
ch[1][u] = ch[1][k], ch[1][k] = u, fa[u] = k, Splay(p, u, 0);
}
else ++ val[k].l, -- val[k].size, Splay(p, k, 0);
}
else {
if(s == x) ++ val[k].l;
else -- val[k].r;
-- val[k].size, Splay(p, k, 0);
}
return x;
}
il LL K_th(int k, int x) {
int u = rt[k];
while(1) {
if(size[ch[0][u]] >= x) u = ch[0][u];
else if(size[ch[0][u]] + val[u].size < x) x -= size[ch[0][u]] + val[u].size, u = ch[1][u];
else return spilt(k, u, x - size[ch[0][u]] + val[u].l - 1);
}
}
}
using namespace splay;
int n, m, q;
signed main() {
n = read(), m = read(), q = read();
rep(i, 1, n) {
rt[i] = ++ tot, val[tot].size = m - 1;
val[tot].l = 1ll * (i - 1ll) * m + 1ll, val[tot].r = 1ll * i * m - 1ll;
}
rep(i, 1, n) insert(0, 1ll * i * m);
while(q --) {
int x = read(), y = read();
if(y == m) {
LL u = K_th(0, x);
printf("%lld
", u), insert(0, u);
}
else {
LL u = K_th(x, y);
printf("%lld
", u), insert(x, K_th(0, x)), insert(0, u);
}
}
return 0;
}