题意不说了，一辈子也忘不掉
解法1.平衡树
这题就是平衡树裸题，每一行开一棵维护前 \(m-1\) 个，最后一列单独维护，因为很多人没有用到，所以平衡树每个节点是一个区间（pair），分裂时顺便把区间裂开来。这也是最暴力的解法
这里以Fhq_Treap为例（其实是我不熟练Splay）
//Fhq_Treap
//http://uoj.ac/submission/296955
#include<stdio.h>
#include<cctype>
#include<cstring>
#include<algorithm>
#define REP(i,a,b) for(int i(a);i<=(b);++i)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
const int S=1<<18;
char ibuf[S],obuf[S+128],*iS,*iT,*oS=obuf,*oT=obuf+S;
#define gc (iS==iT?iT=ibuf+fread(iS=ibuf,1,S,stdin),iS==iT?EOF:*iS++:*iS++)
inline int read(){char c;
while(isspace(c=gc));int w=c&15;
while(isdigit(c=gc))w=w*10+(c&15);return w;
}
inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
#define printf(...) oS>oT&&(flush(),1),oS+=sprintf(oS,__VA_ARGS__)
typedef long long ll;
typedef std::pair<ll,ll>pll;
#define xx first
#define yy second
const int N=3e5+5;
int n,m,cnt,rt[N];
struct node{
int ls,rs,r,siz;
pll w;
}t[N<<3];
#define sz(o) (t[o].w.yy-t[o].w.xx+1)
inline void pushup(int o){t[o].siz=t[t[o].ls].siz+t[t[o].rs].siz+sz(o);}
inline int add(const ll&x,const ll&y){
int o=++cnt;t[o].w=pll(x,y);t[o].siz=y-x+1;
t[o].r=rand();t[o].ls=t[o].rs=0;
return o;
}
inline int merge(int x,int y){
if(!x||!y)return x|y;
if(t[x].r<t[y].r)
return t[x].rs=merge(t[x].rs,y),pushup(x),x;
return t[y].ls=merge(x,t[y].ls),pushup(y),y;
}
void split(int o,int k,int&x,int&y){
if(!k)x=0,y=o;else if(k==t[o].siz)x=o,y=0;
else{
if(k>=t[t[o].ls].siz+sz(o))
split(t[o].rs,k-t[t[o].ls].siz-sz(o),t[o].rs,y),x=o;
else{
if(k<=t[t[o].ls].siz)
split(t[o].ls,k,x,t[o].ls),y=o;
else{
k-=t[t[o].ls].siz;
int p=add(t[o].w.xx+k,t[o].w.yy);
t[o].w.yy=t[p].w.xx-1;
x=o,y=merge(p,t[o].rs);t[o].rs=0;
}
}
pushup(o);
}
}
int main(){
srand((unsigned long long)"THX_AK_NOIP2018");
n=read(),m=read();int q=read();
t[0].w=pll(1,0);
REP(i,1,n)rt[i]=add(1ll*m*(i-1)+1,1ll*i*m-1);
rt[0]=add(m,m);
REP(i,2,n){ll t=1ll*i*m;rt[0]=merge(rt[0],add(t,t));}
while(q--){
int x=read(),y=read(),a,b,c,d,p;
if(y!=m){
split(rt[x],y-1,a,b);
split(b,1,c,d);
rt[x]=merge(a,d);
p=c;
}
split(rt[0],x-1,a,b);
split(b,1,c,d);
if(y!=m)rt[x]=merge(rt[x],c);
rt[0]=merge(a,d);
if(y==m)p=c;
printf("%lld\n",t[p].w.xx);
rt[0]=merge(rt[0],p);
}
return flush(),0;
}
解法2.线段树
同样是每一行和最后一列维护线段树，但是把每次操作看做是新加的节点，最多有 \(Q\) 个
所以线段树值域是 \(max(n,m)+Q\) ，每个节点记录一下被删除节点的总数，然后查第k大时在线段树上二分，找到对应的节点。如果小于 \(n\) 或 \(m\) 就直接算，否则读取存下的 \(id\)
//Segment_Tree
//http://uoj.ac/submission/296972
#include<stdio.h>
#include<cctype>
#include<cstring>
#include<algorithm>
#define REP(i,a,b) for(int i(a);i<=(b);++i)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
const int S=1<<18;
char ibuf[S],obuf[S+128],*iS,*iT,*oS=obuf,*oT=obuf+S;
#define gc (iS==iT?iT=ibuf+fread(iS=ibuf,1,S,stdin),iS==iT?EOF:*iS++:*iS++)
inline int read(){char c;
while(isspace(c=gc));int w=c&15;
while(isdigit(c=gc))w=w*10+(c&15);return w;
}
inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
#define printf(...) oS>oT&&(flush(),1),oS+=sprintf(oS,__VA_ARGS__)
typedef long long ll;
const int N=3e5+5;
struct node{int ls,rs,w;ll id;}t[N*70];
int n,m,q,cnt,c[N],rt[N];
inline void ins(int&o,int l,int r,int x,const ll&y){
if(!o)o=++cnt;
if(l==r){t[o].id=y;return;}
int mid=l+r>>1;
x<=mid?ins(t[o].ls,l,mid,x,y):ins(t[o].rs,mid+1,r,x,y);
}
inline ll del(int&o,int l,int r,int k,int x){
if(!o)o=++cnt;++t[o].w;
if(l==r){
if(!x&&l<=n)return 1ll*l*m;
if(x&&x<=n&&l<m)return 1ll*(x-1)*m+l;
return t[o].id;
}
int mid=l+r>>1,val=mid-l+1-t[t[o].ls].w;
return k<=val?del(t[o].ls,l,mid,k,x):del(t[o].rs,mid+1,r,k-val,x);
}
int main(){
n=read(),m=read(),q=read();int len=std::max(n,m)+q;
#define all 1,len
REP(i,1,n)c[i]=m-1;c[0]=n;
while(q--){
int x=read(),y=read();
ll p,q=del(rt[0],all,x,0);
if(y<m){
p=del(rt[x],all,y,x);
ins(rt[x],all,++c[x],q);
ins(rt[0],all,++c[0],p);
}else ins(rt[0],all,++c[0],q);
printf("%lld\n",y<m?p:q);
}
return flush(),0;
}
解法3.树状数组
考虑把刚刚的线段树用树状数组代替，查第 \(k\) 大可以倍增实现一个log
由于树状数组没办法动态开点，考虑离线下来
刚开始处理时，先把最后一列处理掉，
由于每次操作只会影响当前行和最后一列，因此可以逐行处理，对于每一个操作，倍增查第 \(k\) 大，然后把它删掉，如果这个数小于 \(m\) 则还在原队列里，直接算即可。否则就是最后一列补进来的，在之前处理最后一列的时候已经搞过了
手写了个vector，不过还是没有链表快。。。。
//Binery_Index_Tree
//http://uoj.ac/submission/297045
#include<stdio.h>
#include<cctype>
#include<cstring>
#include<algorithm>
#define REP(i,a,b) for(int i(a);i<=(b);++i)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
const int S=1<<18;
char ibuf[S],obuf[S+128],*iS,*iT,*oS=obuf,*oT=obuf+S;
#define gc (iS==iT?iT=ibuf+fread(iS=ibuf,1,S,stdin),iS==iT?EOF:*iS++:*iS++)
inline int read(){char c;
while(isspace(c=gc));int w=c&15;
while(isdigit(c=gc))w=w*10+(c&15);return w;
}
inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
#define printf(...) oS>oT&&(flush(),1),oS+=sprintf(oS,__VA_ARGS__)
typedef long long ll;
const int N=3e5+5;
typedef std::pair<int,int>pii;
template<typename T>struct vec{
T*a;int n;
vec():a(0),n(0){}
inline T&operator[](const int&i){return a[i];}
inline void clear(){if(n>0)free(a),a=0;n=0;}
inline void pb(const T&x){if((n&-n)==n)a=(T*)realloc(a,(n<<1|1)*sizeof(T));a[n++]=x;}
inline T*begin(){return a;}
inline T*end(){return a+n;}
};
vec<pii>q[N];
vec<int>g[N];
int n,m,Q,c[N<<1],T,t,a[N],pre[N<<1];
inline void clr(int n){
T=n;
for(t=1;t<=T;t<<=1);t>>=1;
REP(i,1,n)c[i]=i&-i;
}
inline void inc(int p){for(;p<=T;p+=p&-p)++c[p];}
inline void dec(int p){for(;p<=T;p+=p&-p)--c[p];}
inline int ask(int k){
int x=0;
for(int p=t;p;p>>=1)if(x+p<=T&&c[x+p]<k)k-=c[x+=p];
return x+1;
}
ll ans[N<<1];
int main(){
n=read(),m=read(),Q=read();
clr(n+Q);
REP(i,1,Q){
int x=read(),y=read();
q[x].pb(pii(y,i+n));dec(y=ask(x));g[x].pb(y);
}
clr(m+Q);
REP(x,1,n){
a[0]=0;
for(pii&u:q[x]){
int y=u.first,id=u.second;
dec(a[++a[0]]=y=ask(y));
if(y<m)ans[id]=1ll*(x-1)*m+y;
else pre[id]=g[x][y-m];
}
REP(i,1,a[0])inc(a[i]);
}
REP(i,1,n)ans[i]=1ll*m*i;
REP(i,n+1,n+Q){
if(pre[i])ans[i]=ans[pre[i]];
printf("%lld\n",ans[i]);
}
return flush(),0;
}