sol
震惊！(NOIP)居然也出数据结构！
话说回来，其实只需要对每一行的前(m-1)个人维护一个数据结构，然后对最后一列的(m)个人也维护一个数据结构就好了。具体的话写平衡树就可以了。
那么对于一次((x,y))的操作，其实就是先把最后一列的第(y)个元素丢到第(x)行里面，再查出第(x)行的第(y)个元素，把他丢到最后一列的最后一个。
现在的问题是：根本开不了(O(nm))的空间啊！
所以就把编号连续的所有点合并成一个点，这样的话初始时就只有(n+n=2n)个点，然后每次查询时会把一个点至多(split)成(3)个，所以总空间复杂度就是(O(n))级别的。
时间复杂度一个(log)。
code
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
int gi()
{
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 3e6+5;
int n,m,q,fa[N],ch[2][N],tot;
ll L[N],R[N],sz[N];
struct Splay{
int root;
int newnode(ll l,ll r)
{
++tot;
L[tot]=l;R[tot]=r;sz[tot]=r-l;
return tot;
}
void pushup(int x)
{
sz[x]=sz[ch[0][x]]+sz[ch[1][x]]+R[x]-L[x];
}
bool son(int x){return x==ch[1][fa[x]];}
void rotate(int x)
{
int y=fa[x],z=fa[y],c=son(x);
ch[c][y]=ch[c^1][x];if (ch[c][y]) fa[ch[c][y]]=y;
fa[x]=z;if (z) ch[son(y)][z]=x;
ch[c^1][x]=y;fa[y]=x;pushup(y);
}
void splay(int x)
{
for (int y=fa[x];y;rotate(x),y=fa[x])
if (fa[y]) son(x)^son(y)?rotate(x):rotate(y);
root=x;pushup(x);
}
int split(int x,ll k)
{
k+=L[x];int y=newnode(k,R[x]);R[x]=k;
if (!ch[1][x]) fa[ch[1][x]=y]=x;
else
{
x=ch[1][x];
while (ch[0][x]) x=ch[0][x];
fa[ch[0][x]=y]=x;
}
splay(y);return y;
}
ll popkth(ll k)
{
int x=root;
while (233)
{
if (k<=sz[ch[0][x]]) x=ch[0][x];
else
{
k-=sz[ch[0][x]];
if (k<=R[x]-L[x])
{
if (k<R[x]-L[x]) split(x,k);
if (k>1) x=split(x,k-1);
break;
}
else k-=R[x]-L[x],x=ch[1][x];
}
}
splay(x);
fa[ch[0][x]]=fa[ch[1][x]]=0;
if (!ch[0][x]) root=ch[1][x];
else
{
int y=ch[0][x];
while (ch[1][y]) y=ch[1][y];
splay(y);
root=fa[ch[1][y]=ch[1][x]]=y;
pushup(y);
}
return L[x];
}
void pushback(ll k)
{
int y=newnode(k,k+1);
if (!root) root=y;
else{
int x=root;
while (ch[1][x]) x=ch[1][x];
splay(x);
fa[ch[1][x]=y]=x;pushup(x);
}
}
}S[N];
int main()
{
n=gi();m=gi();q=gi();
for (int i=1;i<=n;++i) S[i].root=S[i].newnode(1ll*(i-1)*m+1,1ll*i*m);
for (int i=1;i<=n;++i) S[0].pushback(1ll*i*m);
while (q--)
{
int x=gi(),y=gi();ll ans;
S[x].pushback(S[0].popkth(x));
printf("%lld
",ans=S[x].popkth(y));
S[0].pushback(ans);
}
return 0;
}