https://www.luogu.com.cn/problem/P3960
看有写平衡树的，不过其实发现由于这个题插入的点都是在边上，所以完全可以用一个动态开点的线段树来做
用 (n+1) 个线段树来维护，前 (n) 个分别维护 (n) 行的 (1) 到 (m-1) 位置的点，第 (n+1) 棵维护第 (m) 列 (n) 个位置的信息
有很多组点，它们始终是一起运动的，所以也就没必要把它们都拿出来单独分配内存，这也是动态开点的目的
每次当取出 ((x,y)) 时：
- 如果 (y
eq m)，就去第 (x) 个线段树取出第 (y) 个点，删除它（如何实现删除？其实就是维护一个 (size)，然后递归时用 (size) 判断进左儿子还是右儿子），再把他添加到第 (n+1) 个树的末尾（代表了那个离队的同学归队，同时由于动态开店的线段树也要在一开始就确定长度，所以每个树的大小应为 (max(n,m)+q)）
然后第 (x) 行同学往左补队的时候，((x,m)) 的位置，离开第 (n+1) 棵线段树，进入第 (x) 棵 - 如果 (y=m)，就直接取出 (n+1) 棵线段树的第 (x) 个点，再放到最后。然后就没有往左补队的那一套了
发现上述过程并没有体现出某一个区间的位置整体移动的过程，也正是因此保证了复杂度
其实刚才说的删除点更像是惰性删除，只是减小 (size) 从而让这个点不会再被访问到，这个在线段树上删除点的思路在之前似乎还没见到过
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
int n,m;
int num[300006];
struct tr{
tr *ls,*rs;
long long w;
int size;
}dizhi[30000006];
int tot;
struct segment{
tr *root;
inline int get(int l,int r,int now){
if(now==n+1){
if(r<=n) return r-l+1;
if(l<=n) return n-l+1;
return 0;
}
if(r<m) return r-l+1;
if(l<m) return m-l;
return 0;
}
long long ask(tr *&tree,int l,int r,int pos,int now){
if(!tree){
tree=&dizhi[++tot];
tree->size=get(l,r,now);
if(l==r){
if(now==n+1) tree->w=(long long)l*m;
else tree->w=(long long)(now-1)*m+l;
}
}
tree->size--;
if(l==r) return tree->w;
int mid=(l+r)>>1;
if((tree->ls&&pos<=tree->ls->size)||(!tree->ls&&pos<=mid-l+1))
return ask(tree->ls,l,mid,pos,now);
if(!tree->ls) pos-=mid-l+1;
else pos-=tree->ls->size;
return ask(tree->rs,mid+1,r,pos,now);
}
void change(tr *&tree,int l,int r,int pos,long long w,int now){
if(!tree){
tree=&dizhi[++tot];
tree->size=get(l,r,now);
if(l==r) tree->w=w;
}
tree->size++;
if(l==r) return;
int mid=(l+r)>>1;
pos<=mid?change(tree->ls,l,mid,pos,w,now):change(tree->rs,mid+1,r,pos,w,now);
}
}tree[300006];
int main(){
n=read();m=read();int q=read();
reg int x,y;long long tmp;
int len=std::max(n,m)+q;
for(reg int i=1;i<=n+1;i++) tree[i].root=&dizhi[++tot],tree[i].root->size=m;
tree[n+1].root->size=n;//root 的 size 提前设置
while(q--){
x=read();y=read();
if(y==m) printf("%lld
",tmp=tree[n+1].ask(tree[n+1].root,1,len,x,n+1));
else printf("%lld
",tmp=tree[x].ask(tree[x].root,1,len,y,x));
tree[n+1].change(tree[n+1].root,1,len,n+(++num[n+1]),tmp,n+1);
if(y^m){
tmp=tree[n+1].ask(tree[n+1].root,1,len,x,n+1);
// printf(" tmp=%d
",tmp);
tree[x].change(tree[x].root,1,len,m-1+(++num[x]),tmp,x);
}
}
return 0;
}