代码

#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;

const int maxn=3000100;
typedef long long ll;
int n,m,Q,tot,root[maxn];
struct node
{
	int fa,ch[2];
	ll lval,rval,siz;
}a[maxn];
queue<int>q;
#define R register
#define I inline

I bool get(R int x)
{
	return x==a[a[x].fa].ch[1];
}

I void update(R int x)
{
	a[x].siz=a[a[x].ch[0]].siz+a[a[x].ch[1]].siz+a[x].rval-a[x].lval+1;
}

I int newnode(R ll lv,R ll rv)
{
	R int x;
	if (!q.empty())
	{
		x=q.front();
		q.pop();
	}
	else
		x=++tot;
	a[x].fa=a[x].ch[0]=a[x].ch[1]=0;
	a[x].lval=lv;
	a[x].rval=rv;
	a[x].siz=rv-lv+1;
	return x;
}

I void rotate(R int x)
{
	int y=a[x].fa,z=a[y].fa,k=get(x),w=a[x].ch[k^1];
	a[y].ch[k]=w;
	a[w].fa=y;
	a[z].ch[get(y)]=x;
	a[x].fa=z;
	a[x].ch[k^1]=y;
	a[y].fa=x;
	update(y);
	update(x);
}

I void splay(R int x,R int id)
{
	R int y,z;
	while (a[x].fa)
	{
		y=a[x].fa,z=a[y].fa;
		if (z)
		{
			if (get(x)^get(y))
				rotate(x);
			else
				rotate(y);
		}
		rotate(x);
	}
	root[id]=x;
}

I void push_back(R int id,R ll lv,R ll rv)
{
	R int x=newnode(lv,rv);
	if (!root[id])
	{
		root[id]=x;
		return;
	}
	R int rt=root[id];
	while (a[rt].ch[1])
		rt=a[rt].ch[1];
	splay(rt,id);
	a[rt].ch[1]=x;
	a[x].fa=rt;
	update(rt);
}

I int split(R int id,R int x,R ll k)
{
	R int y=newnode(a[x].lval+k,a[x].rval);
	a[x].rval=a[x].lval+k-1;
	if (!a[x].ch[1])
	{
		a[x].ch[1]=y;
		a[y].fa=x;
		splay(y,id);
		return y;
	}
	R int t=a[x].ch[1];
	while (a[t].ch[0])
		t=a[t].ch[0];
	a[t].ch[0]=y;
	a[y].fa=t;
	while (t^x)
	{
		update(t);
		t=a[t].fa;
	}
	splay(y,id);
	return y;
}

I ll pop_kth(R int id,R ll k)
{
	R int x=root[id];
	while (1)
	{
		if (a[a[x].ch[0]].siz>=k)
			x=a[x].ch[0];
		else
		{
			k-=a[a[x].ch[0]].siz;
			if (k<=a[x].rval-a[x].lval+1)
			{
				if (k^(a[x].rval-a[x].lval+1))
					split(id,x,k);
				if (k^1)
					x=split(id,x,k-1);
				break;
			}
			else
			{
				k-=a[x].rval-a[x].lval+1;
				x=a[x].ch[1];
			}
		}
	}
	splay(x,id);
	a[a[x].ch[0]].fa=a[a[x].ch[1]].fa=0;
	if (!a[x].ch[0])
	{
		root[id]=a[x].ch[1];
		q.push(x);
		return a[x].lval;
	}
	int t=a[x].ch[0];
	while (a[t].ch[1])
		t=a[t].ch[1];
	splay(t,id);
	a[t].ch[1]=a[x].ch[1];
	a[a[x].ch[1]].fa=t;
	update(t);
	q.push(x);
	return a[x].lval;
}

char buf[1000001],*p1=buf,*p2=buf;

I char get_char()
{
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}

I int read()
{
	R int x=0;
	R char c=get_char();
	while (c<48||c>57)
		c=get_char();
	while (c>=48&&c<=57)
		x=(x<<1)+(x<<3)+(c^48),c=get_char();
	return x;
}

void write(ll x)
{
	if (x>9)
		write(x/10);
	putchar(x%10+48);
}

int main()
{
	R int i,j;
	R ll val;
	n=read(),m=read(),Q=read();
	for (i=1;i<=n;i++)
	{
		push_back(i,1ll*(i-1)*m+1,1ll*(i-1)*m+m-1);
		push_back(0,1ll*i*m,1ll*i*m);
	}
	while (Q--)
	{
		i=read(),j=read();
		if (j==m)
		{
			val=pop_kth(0,1ll*i);
			push_back(0,val,val);
			write(val);
			puts("");
		}
		else
		{
			val=pop_kth(0,1ll*i);
			push_back(i,val,val);
			val=pop_kth(i,1ll*j);
			push_back(0,val,val);
			write(val);
			puts("");
		}
	}
	return 0;
}

评测结果