洛谷题目页面传送门
题意见洛谷。
方法(1)：平衡树
不难发现，行与行之间的操作是独立的，而都与最后一列有关。很自然地想到维护每一行的前(m-1)个元素和最后一列。
不难发现，一次((x,y))离队，可以分成两种情况：
- (y=m)。可以看作将最后一列的第(x)个移到最后；
- (y
eq m)。可以看作：
- 将第(x)行第(y)个移到最后一列最后；
- 将最后一列第(x)个移到第(x)行最后。
这些维护序列的删除、插入、查询第(k)个，一看就是序列之王平衡树的操作，这里使用fhq-Treap。
至于，如果暴力维护平衡树的话，建树就要MLE，是(mathrm O(nm))的。考虑用fbb的OJ那题的trick，任意时刻，所有没有被拎出来的naive元素组成的极大区间（区间内编号连续），我们把它们缩成一个点。
代码里操作能合并的合并，修改操作也可以返回原值减少操作量，来减小常数，毕竟这不是正解/cy
由于要删除节点，我开了垃圾回收，其实根本不用，就当练习一下（
一开始觉得挺难，现在看来是个挺板的题啊。。时间复杂度(mathrm O(qlog n))（假设(n,m)同阶）。
这里讲一个我代码里犯的稀有的错误：这是我第一次用vector存节点写平衡树，其中建树的时候我是这样写的：
if(l<mid)lson(p)=bld(l,mid-1);
if(r>mid)rson(p)=bld(mid+1,r);
以第一句为例，这里lson(p)和bld(l,mid-1)的执行顺序直觉是先后者后前者，但其实不是，究竟是先前者后后者还是UB我也说不清，详见这篇帖子。问题来了，bld函数会调用nwnd函数新建节点并调用vector的push_back函数，这会使vector重新分配内存，导致lson(p)的地址变了，进而导致值赋不进去。我调这个代码的那天晚上还以为闹鬼了，差点把我整哭了（捂脸
所以应该找个中间变量存下来：
int res;
if(l<mid)res=bld(l,mid-1),lson(p)=res;
if(r>mid)res=bld(mid+1,r),rson(p)=res;
代码（开洛谷自带O2才能过哦，毒瘤）：
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define X first
#define Y second
typedef long long ll;
mt19937 rng(20060617);
const int N=300000;
int n,m,qu;
struct fhq_treap{//平衡树
int root;
struct node{unsigned key;int lson,rson,sz,real_sz;ll l,r;};
#define key(p) nd[p].key
#define lson(p) nd[p].lson
#define rson(p) nd[p].rson
#define sz(p) nd[p].sz
#define real_sz(p) nd[p].real_sz
#define l(p) nd[p].l
#define r(p) nd[p].r
vector<node> nd;//vector存节点
stack<int> bin;//垃圾桶
int nwnd(ll l,ll r){//新建节点
if(l>r)return 0;
if(bin.size()){//用垃圾
int p=bin.top();
bin.pop();
return nd[p]=node({rng(),0,0,1,int(r-l+1),l,r}),p;
}
return nd.pb(node({rng(),0,0,1,int(r-l+1),l,r})),nd.size()-1;
}
void sprup(int p){sz(p)=sz(lson(p))+1+sz(rson(p));real_sz(p)=real_sz(lson(p))+r(p)-l(p)+1+real_sz(rson(p));}
int bld(int l=1,int r=n){//建树
int mid=l+r>>1,p=nwnd(1ll*mid*m,1ll*mid*m);
int res;
if(l<mid)res=bld(l,mid-1),lson(p)=res;
if(r>mid)res=bld(mid+1,r),rson(p)=res;//讷，错误就在这里
sprup(p);
return sprup(p),p;
}
void init(ll l=0,ll r=0){
nd.pb(node({0,0,0,0,0,0,0}));
if(l)root=nwnd(l,r);
else root=bld();
}
pair<int,int> split(int x,int p=-1){~p||(p=root);
if(!x)return mp(0,p);
pair<int,int> sp;
if(x<=sz(lson(p)))return sp=split(x,lson(p)),lson(p)=sp.Y,sprup(p),mp(sp.X,p);
return sp=split(x-1-sz(lson(p)),rson(p)),rson(p)=sp.X,sprup(p),mp(p,sp.Y);
}
int mrg(int p,int q){
if(!p||!q)return p|q;
if(key(p)<key(q))return rson(p)=mrg(rson(p),q),sprup(p),p;
return lson(q)=mrg(p,lson(q)),sprup(q),q;
}
pair<int,int> rk(int x,int p=-1){~p||(p=root);//在树中的排名（算naive区间）
if(x<=real_sz(lson(p)))return rk(x,lson(p));
if(x<=real_sz(lson(p))+r(p)-l(p)+1)return mp(sz(lson(p))+1,x-real_sz(lson(p)));
pair<int,int> res=rk(x-(real_sz(lson(p))+r(p)-l(p)+1),rson(p));
return mp(sz(lson(p))+1+res.X,res.Y);
}
void recyc(int p){bin.push(p);}//垃圾回收
ll del(int x){//删除点
pair<int,int> _rk=rk(x);
pair<int,int> sp=split(_rk.X-1),sp0=split(1,sp.Y);
node tmp=nd[sp0.X];
recyc(sp0.X);//垃圾回收
int l=nwnd(tmp.l,tmp.l+_rk.Y-2),r=nwnd(tmp.l+_rk.Y,tmp.r);
return root=mrg(sp.X,mrg(l,mrg(r,sp0.Y))),tmp.l+_rk.Y-1;
}
ll chg_mv_bk(int x,ll v=0){//修改并移到最后
pair<int,int> _rk=rk(x);
pair<int,int> sp=split(_rk.X-1),sp0=split(1,sp.Y);
ll res=l(sp0.X)+_rk.Y-1;
int l=nwnd(l(sp0.X),l(sp0.X)+_rk.Y-2),r=nwnd(l(sp0.X)+_rk.Y,r(sp0.X));
l(sp0.X)=r(sp0.X)=v?v:res,real_sz(sp0.X)=1;
return root=mrg(sp.X,mrg(l,mrg(r,mrg(sp0.Y,sp0.X)))),res;
}
void pb(ll v){//在最后压入
root=mrg(root,nwnd(v,v));
}
}trp_r[N+1],&trp_c=trp_r[0];
int main(){
cin>>n>>m>>qu;
for(int i=1;i<=n;i++)trp_r[i].init(1ll*(i-1)*m+1,1ll*i*m-1);
trp_c.init();//最后一列要普通建树，因为编号不连续/kk
while(qu--){
int x,y;
scanf("%d%d",&x,&y);
if(y==m){//情况1
printf("%lld
",trp_c.chg_mv_bk(x));
}
else{//情况2
ll res=trp_r[x].del(y);
printf("%lld
",res);
trp_r[x].pb(trp_c.chg_mv_bk(x,res));
}
}
return 0;
}
方法(2)：动态开点线段树
回想当年不会平衡树的时候，想着咋用现有知识维护序列插入删除。一个想法是：给每个位置设一个值(0/1)，(1)表示还健在，(0)表示被删了。删除操作就赋(0)，查询第(k)个就二分出前缀和等于(k)的第一个位置，那么插入呢？就无能为力了。幸运的是，这题的插入操作只存在于末尾，于是我们在末尾直接新建节点即可。考虑到空间开不下，我们用动态开点线段树维护，查询的话线段树二分。然后大概也是跟平衡树一样缩点。
代码很难写，不想写了。常数应该小一点？
方法(3)：BIT（正解）
考虑继续缩小常数。注意到，单点查询和在前缀和上二分（BIT倍增，这里由于BIT只能从左往右倍增最右值，而我们要查最左边的(geq k)的位置，只需要转化为最右边的(<k)的位置加一即可）刚好都是BIT能支持的，考虑使用BIT。
但是BIT不能动态开点，空间受不了怎么办呢？
考虑这样一个方法：将询问离线下来，依次处理每行的前(m-1)个元素（每行内部按时间戳排序），把查询的结果记下来，处理完之后撤销影响处理下一个，这样空间只需要开一个BIT，时间复杂度也是不变的。
由于没有按原顺序操作，我们并不能知道每个位置的具体编号。这样再从头按原顺序来一遍，此时每个行都不需要BIT了，把BIT留给最后一列实时操作，每行及最后一列开个vector记录插入末尾的编号，就可以实时查询任意合法位置的编号了。
代码（不开O2也每个点在(1mathrm s)内）：
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
int lowbit(int x){return x&-x;}
const int N=300000,QU=300000;
int n,m,qu;
struct query{int x,y,id;}qry[QU+1];
bool cmp(query x,query y){return x.id<y.id;}
vector<query> v[N+1];
struct bitree{//BIT
int sum[N+QU+1];
void init(){memset(sum,0,sizeof(sum));}
void add(int x,int v){//单点加
while(x<=max(n,m)+qu)sum[x]+=v,x+=lowbit(x);
}
int fd(int x){//BIT倍增
int res=0,now=0;
for(int i=20;~i;i--)if(res+(1<<i)<=max(n,m)+qu&&now+sum[res+(1<<i)]<x)res+=1<<i,now+=sum[res];
return res+1;
}
}bit;
int fd[N+1];//记录查询结果
vector<ll> bk_r[N+1],&bk_c=bk_r[0];
int main(){
cin>>n>>m>>qu;
for(int i=1;i<=qu;i++)scanf("%d%d",&qry[i].x,&qry[i].y),qry[i].id=i,qry[i].y<m&&(v[qry[i].x].pb(qry[i]),0);
bit.init();//初始化
for(int i=1;i<m;i++)bit.add(i,1);
for(int i=1;i<=n;i++){//离线操作
sort(v[i].begin(),v[i].end(),cmp);//按时间戳排序
for(int j=0;j<v[i].size();j++){
int y=v[i][j].y,id=v[i][j].id;
fd[id]=bit.fd(y);//查询并记录
bit.add(fd[id],-1);bit.add(m+j,1);//删除、插入
}
for(int j=0;j<v[i].size();j++)bit.add(fd[v[i][j].id],1),bit.add(m+j,-1);//撤销影响
}
bit.init();//重置
for(int i=1;i<=n;i++)bit.add(i,1);
for(int i=1;i<=qu;i++){
int x=qry[i].x,y=qry[i].y;
if(y==m){
int _fd=bit.fd(x);
ll res=_fd<=n?1ll*_fd*m:bk_c[_fd-n-1];//从vector里查
printf("%lld
",res);
bk_c.pb(res);//压入vector
bit.add(_fd,-1);bit.add(n+bk_c.size(),1);//删除、插入
}
else{
ll res=fd[i]<m?1ll*(x-1)*m+fd[i]:bk_r[x][fd[i]-m];//从vector里查
printf("%lld
",res);
int _fd=bit.fd(x);
bk_r[x].pb(_fd<=n?1ll*_fd*m:bk_c[_fd-n-1]);bk_c.pb(res);//压入vector
bit.add(_fd,-1);bit.add(n+bk_c.size(),1);//删除、插入
}
}
return 0;
}