Description
Sylvia 是一个热爱学习的女孩子。
前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。Sylvia所在的方阵中有n × m名学生，方阵的行数为 n，列数为 m。
为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中的学生从 1 到 n × m 编上了号码（参见后面的样例）。即：初始时，第 i 行第 j 列的学生的编号是(i - 1) × m + j。
然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天中，一共发生了 q 件这样的离队事件。每一次离队事件可以用数对(x, y) (1≤x≤n,1≤y≤m)描述，表示第 x 行第 y 列的学生离队。
在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达这样的两条指令：
1. 向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条指令之后，空位在第 x 行第 m 列。
2. 向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条指令之后，空位在第 n 行第 m 列。
教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后，下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第 n 行第 m 列一个空位，这时这个学生会自然地填补到这个位置。
因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学的编号是多少。
注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后方阵中同学的编号可能是乱序的。
Input
输入文件名为 phalanx.in。
输入共 q+1 行。
第 1 行包含 3 个用空格分隔的正整数 n, m, q，表示方阵大小是 n 行 m 列，一共发生了 q 次事件。
接下来 q 行按照事件发生顺序描述了 q 件事件。每一行是两个整数 x, y，用一个空格分隔，表示这个离队事件中离队的学生当时排在第 x 行第 y 列。
Output
输出文件名为 phalanx.out。
按照事件输入的顺序，每一个事件输出一行一个整数，表示这个离队事件中离队学生的编号。
Sample Input
2 2 3
1 1
2 2
1 2
Sample Output
1
1
4
Hint
线段树
好像是第一次写这种线段树维护区间插入/删除的题（因为听说splay常数大，不敢写）。
首先肯定将第m列与那n行分开维护，一共有n+1颗线段树。
我们首先将对应的节点打上标记，表示该节点并没有改变，当我们需要访问其子区间的时候，将该区间拆成两个。然后询问(x,y)(x,y)(x,y)的时候，假设y!=my!=my!=m，那么就是找第x行的第y个数。否则就是找第m行的第x个数。找数的过程就是线段树上二分，具体来说我们对每个区间要记录一个sizesizesize表示区间内的人数。然后在将对应区间的sizesizesize减少。插入的时候直接插入在区间的最后就行了。
每一行最多n+mn+mn+m个点，所以动态开点上界设在n+mn+mn+m就可以了。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<ctime>
#include<queue>
#include<iomanip>
#define ll long long
#define N 300005 using namespace std;
inline int Get() {int x=,f=;char ch=getchar();while(ch<''||ch>'') {if(ch=='-') f=-;ch=getchar();}while(''<=ch&&ch<='') {x=(x<<)+(x<<)+ch-'';ch=getchar();}return x*f;} ll n,m,q;
int cnt;
int nxt[N];
const int lx=,rx=N<<;
int rt[N];
int tag[N*],ls[N*],rs[N*],size[N*];
ll id[N*];
void update(int v) {size[v]=size[ls[v]]+size[rs[v]];} void build(int &v,int l,int r) {
if(!v) v=++cnt;
size[v]=r-l+;
if(l==r) id[v]=l;
tag[v]=;
} void pre(int &v,int l,int r,int lx,int rx) {
if(!v) v=++cnt;
if(l>rx||r<lx) return ;
if(l<=lx&&rx<=r) {build(v,lx,rx);return ;}
int mid=lx+rx>>;
pre(ls[v],l,r,lx,mid);
pre(rs[v],l,r,mid+,rx);
update(v);
} void Find(int v,int lx,int rx,int k,ll &pos,ll &g) {
if(lx==rx) {
pos=lx;
g=id[v];
return ;
}
int mid=lx+rx>>;
if(tag[v]) {
build(ls[v],lx,mid);
build(rs[v],mid+,rx);
tag[v]=;
}
if(k>size[ls[v]]) {
Find(rs[v],mid+,rx,k-size[ls[v]],pos,g);
} else {
Find(ls[v],lx,mid,k,pos,g);
}
} void Delete(int v,int lx,int rx,int pos) {
size[v]--;
if(lx==rx) return ;
int mid=lx+rx>>;
if(tag[v]) {
build(ls[v],lx,mid);
build(rs[v],mid+,rx);
tag[v]=;
}
if(pos<=mid) Delete(ls[v],lx,mid,pos);
else Delete(rs[v],mid+,rx,pos);
} void Insert(int &v,int lx,int rx,int pos,ll id) {
if(!v) v=++cnt;
size[v]++;
if(lx==rx) {
::id[v]=id;
return ;
}
int mid=lx+rx>>;
if(tag[v]) {
build(ls[v],lx,mid);
build(rs[v],mid+,rx);
tag[v]=;
}
if(pos<=mid) Insert(ls[v],lx,mid,pos,id);
else Insert(rs[v],mid+,rx,pos,id);
} ll pos,g; void Get_out(ll &nx,ll &ny,ll x,ll y) {
if(y<m) {
Find(rt[x],lx,rx,y,pos,g);
if(pos<=m-) {
nx=x;
ny=pos;
} else {
nx=(g-)/m+;
ny=(g-)%m+;
}
Delete(rt[x],lx,rx,pos);
} else {
Find(rt[n+],lx,rx,x,pos,g);
if(pos<=n) {
nx=pos;
ny=m;
} else {
nx=(g-)/m+;
ny=(g-)%m+;
}
Delete(rt[n+],lx,rx,pos);
}
} int main() {
n=Get(),m=Get(),q=Get();
if(m>) {
for(int i=;i<=n;i++) {
nxt[i]=m;
pre(rt[i],,m-,lx,rx);
}
}
pre(rt[n+],,n,lx,rx);
nxt[n+]=n+;
int x,y;
ll sx,sy;
ll tx,ty;
while(q--) {
x=Get(),y=Get();
if(y<m) {
Get_out(sx,sy,x,y);
Get_out(tx,ty,x,m);
Insert(rt[x],lx,rx,nxt[x],(tx-)*m+ty);
Insert(rt[n+],lx,rx,nxt[n+],(sx-)*m+sy);
nxt[x]++,nxt[n+]++;
} else {
Get_out(sx,sy,x,y);
Insert(rt[n+],lx,rx,nxt[n+],(sx-)*m+sy);
nxt[n+]++;
}
cout<<(sx-)*m+sy<<"\n";
}
return ;
}