题目大意
在(n*m)的矩阵中每个位置开始都按顺序编号
每次都对一个位置((x,y))操作：
先取出((x,y))
将((x,y))右侧所有位置左移一格
再将最后一列空位下方向上移
最后将((x,y))插回位置((n,m))
每次输出操作位置((x,y))的编号
(1 leq n,m,q leq 3*10^5)
解题思路
平衡树好题，用fhq Treap写
首先，一个朴素的想法是，对每一行([1,m-1])分别建立一棵平衡树，再对最后一列建立一棵平衡树
每次只要对第x行第y个数操作即可（基础的操作）
但是数据范围不允许我们对每一个位置建一个结点
那么我们考虑可否把多个位置压进一个结点储存？
我们可以令每个结点表示一段连续的编号
注意最后一列因为编号不连续，没有办法压进一个结点，只能用(O(n))建树的方法把所有结点都加入
举个例子
例如(5*5)的矩阵第二行的Treap中初始只包含一个结点((6,9))
它代表了(6sim 9)编号的位置
当我们查询((x=2,y=3))位置的时候就先把((6,9))取出，把它分成((6,7),(8,8),(9,9))
这样一来，不仅编号没有丢失，都维护了起来，而且拆出了我们要求的结点((8,8))
然后再在最后一列的Treap中拆出((10,10))（需要向左移的结点）
于是我们合并((6,7),(9,9),(10,10))成为一颗Treap就维护好了第二行
不过要注意我们是按位置拆分合并，而不是按值
#include<iostream>
#include<cstdio>
#include<cstdlib>
long long n,m,Q,x,y;
namespace BST{
struct node{
int L,R,ran;
long long l,r,size;
}T[10000000];
int tot;
int root[500000],Root;
inline void update(int x){T[x].size=T[T[x].L].size+T[T[x].R].size+T[x].r-T[x].l+1;}
void get_size(int now){
if (T[now].L) get_size(T[now].L);
if (T[now].R) get_size(T[now].R);
update(now);
}
void build(){
for (int i=1;i<=n;i++){
root[i]=i;
T[++tot]=(node){0,0,rand(),(i-1)*m+1,i*m-1,m-1};
}
int stk[500000],top=0,last;
for (int i=1;i<=n;i++){
T[++tot]=(node){0,0,rand(),i*m,i*m,1};
last=0;
while (top&&T[tot].ran>T[stk[top]].ran) last=stk[top--];
T[tot].L=last;
T[stk[top]].R=tot;
stk[++top]=tot;
}
Root=stk[1];
get_size(Root);
}
void splitl(int now,int k,int &x,int &y){
if (!now){x=y=0;return;}
if (k<=T[T[now].L].size+T[now].r-T[now].l+1){
y=now;splitl(T[now].L,k,x,T[now].L);
}
else{
x=now;splitl(T[now].R,k-(T[T[now].L].size+T[now].r-T[now].l+1),T[now].R,y);
}
update(now);
}
void splitr(int now,long long k,int &x,int &y){
if (!now){x=y=0;return;}
if (k<=T[T[now].L].size){
y=now;splitr(T[now].L,k,x,T[now].L);
}
else{
x=now;splitr(T[now].R,k-(T[T[now].L].size+T[T[now].L].r-T[T[now].L].l+1),T[now].R,y);
}
update(now);
}
int merge(int x,int y){
if (!(x&&y)) return x|y;
if (T[x].ran>T[y].ran){
T[x].R=merge(T[x].R,y);
update(x);
return x;
}
else{
T[y].L=merge(x,T[y].L);
update(y);
return y;
}
}
void splitnode(int p,long long k,int &L,int &M,int &R){
L=M=R=0;
if (k>1){T[++tot]=(node){0,0,rand(),T[p].l,T[p].l+k-2,k-1};L=tot;}
if (k<T[p].size){T[++tot]=(node){0,0,rand(),T[p].l+k,T[p].r,T[p].r-T[p].l-k+1};R=tot;}
T[++tot]=(node){0,0,rand(),T[p].l+k-1,T[p].l+k-1,1};M=tot;
}
}
int main(){
scanf("%d%d%d",&n,&m,&Q);
BST::build();
for (int i=1;i<=Q;i++){
scanf("%d%d",&x,&y);
if (y!=m){
int a,b,c,d,e,f,g;
BST::splitl(BST::root[x],y,a,b);
BST::splitr(b,1,b,c);
BST::splitnode(b,y-BST::T[a].size,d,e,f);
printf("%lld
",BST::T[e].l);
a=BST::merge(a,d);
c=BST::merge(f,c);
BST::splitl(BST::Root,x,d,f);
BST::splitr(f,1,f,g);
BST::root[x]=BST::merge(BST::merge(a,c),f);
BST::Root=BST::merge(BST::merge(d,g),e);
}
else{
int a,b,c;
BST::splitl(BST::Root,x,a,b);
BST::splitr(b,1,b,c);
printf("%lld
",BST::T[b].l);
BST::Root=BST::merge(BST::merge(a,c),b);
}
}
}