代码

#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;

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

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

int newnode(ll lv,ll rv)
{
	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;
}

void rotate(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);
}

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

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

int split(int id,int x,ll k)
{
	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;
	}
	else
	{
		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,0);
	return y;
}

ll pop_kth(int id,ll k)
{
	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,0);
	a[a[x].ch[0]].fa=a[a[x].ch[1]].fa=0;
	if (!a[x].ch[0])
		root[id]=a[x].ch[1];
	else
	{
		int t=a[x].ch[0];
		while (a[t].ch[1])
			t=a[t].ch[1];
		splay(t,id,0);
		a[t].ch[1]=a[x].ch[1];
		a[a[x].ch[1]].fa=t;
		update(t);
	}
	q.push(x);
	return a[x].lval;
}

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

int main()
{
	int i,j;
	ll val;
	n=read(),m=read(),Q=read();
	for (i=1;i<=n;i++)
	{
		push_back(i,1ll*(1ll*(i-1)*m+1),1ll*(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);
			printf("%lld\n",val);
		}
		else
		{
			val=pop_kth(0,1ll*i);
			push_back(i,val,val);
			val=pop_kth(i,1ll*j);
			push_back(0,val,val);
			printf("%lld\n",val);
		}
	}
	return 0;
}

评测结果