维护一个方阵，支持
1.删掉一个点，剩下的点先向左看齐再向前看齐
2.询问一个位置上是哪个点
$n,m,q leq 3 imes 10^5$
sol：
我们每行前$m-1$列维护一个线段树，最后一列维护一棵线段树
然后搞n + 1个vector
这个线段树只需要维护“这个节点下面有多少点已经被删除了”
删除最后一列时，删掉一个点然后pushback即可
非最后一列时，删掉这个点，把它加到最后一列最下面，然后把本来应该在这个位置的数放到这一行最后就可以了
之前写过splay。。。线段树好写好多啊QAQ
#include<bits/stdc++.h> #define LL long long using namespace std; inline int read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } const int maxn = 20000005,maxm = 600010; int n,m,q,mx; vector<LL> vec[maxn]; int ls[maxn],rs[maxn],val[maxn],dfn,root[maxn]; inline void modify(int &x,int l,int r,int pos) { if(!x)x = ++dfn;val[x]++; if(l == r)return; int mid = (l + r) >> 1; if(pos <= mid)modify(ls[x],l,mid,pos); else modify(rs[x],mid + 1,r,pos); } inline int query(int x,int l,int r,int pos) { if(l == r)return l; int mid = (l + r) >> 1,sizel = mid - l + 1 - val[ls[x]]; if(sizel >= pos)return query(ls[x],l,mid,pos); else return query(rs[x],mid + 1,r,pos - sizel); } inline LL delete_r(int x,LL v) { int pos = query(root[n + 1],1,mx,x); modify(root[n + 1],1,mx,pos); LL ans = pos <= n ? 1LL * pos * m : vec[n + 1][pos - n - 1]; vec[n + 1].push_back(v ? v : ans); return ans; } inline LL delete_l(int x,int y) { int pos = query(root[x],1,mx,y); modify(root[x],1,mx,pos); LL ans = pos < m ? 1LL * (x - 1) * m + pos : vec[x][pos - m]; vec[x].push_back(delete_r(x,ans)); return ans; } int main() { n = read();m = read(),q = read(); mx = max(n,m) + q; while(q--) { int x = read(),y = read(); LL ans; if(y == m)ans = delete_r(x,0); else ans = delete_l(x,y); printf("%lld ",ans); } }