代码

/*
splay 100pts

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

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);
			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;
}

*/

/*
Binary Index Tree+vector(the official solution) 100pts
*/

#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;

const int maxn=3000010;
typedef long long ll;
int n,m,Q,len,qx[maxn],qy[maxn],pre[maxn];
struct node
{
	int pos,id;
};
vector<node>v[maxn];
vector<ll>q[maxn];
ll c[maxn<<1],ans;

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 lowbit(int x)
{
	return x&-x;
}

void update(int x,ll val)
{
	for (;x<=len;x+=lowbit(x))
		c[x]+=val;
}

ll query(int x)
{
	ll res=0;
	for (;x;x-=lowbit(x))
		res+=c[x];
	return res;
}

int kth(int k)
{
	int l=0,r=len,mid,tmp;
	while (l<=r)
	{
		mid=(l+r>>1);
		if (query(mid)>=k)
			r=mid-1,tmp=mid;
		else
			l=mid+1;
	}
	return tmp;
}

int main()
{
	int i,j,siz;
	node u;
	n=read(),m=read(),Q=read();
	len=max(n,m)+Q;
	for (i=1;i<=len;i++)
		update(i,1);
	for (i=1;i<=Q;i++)
	{
		qx[i]=read(),qy[i]=read();
		if (qy[i]!=m)
			v[qx[i]].push_back((node){qy[i],i});
	}
	for (i=1;i<=n;i++)
	{
		siz=v[i].size();
		for (j=0;j<siz;j++)
		{
			u=v[i][j];
			pre[u.id]=kth(u.pos);
			update(pre[u.id],-1);
		}
		for (j=0;j<siz;j++)
			update(pre[v[i][j].id],1);
	}
	for (i=1;i<=Q;i++)
	{
		j=kth(qx[i]);
		ans=(j<=n?1ll*j*m:q[0][j-n-1]);
		update(j,-1);
		if (qy[i]!=m)
		{
			q[qx[i]].push_back(ans);
			ans=(pre[i]<m?1ll*(qx[i]-1)*m+pre[i]:q[qx[i]][pre[i]-m]);
		}
		q[0].push_back(ans);
		printf("%lld\n",ans);
	}
	return 0;
}

评测结果