代码

#include<stdio.h>
#include<vector>
#define N 1000005
#define int long long
using namespace std;
int n,m,q,X;
vector<int>v[N<<3];
int rt[N<<3];
struct segment_tree{
	#define mid ((l+r)>>1)
	int sum[N<<3],ls[N<<3],rs[N<<3],tot=0;
	void modify(int &k,int l,int r,int pos){
		if(!k)k=++tot; ++sum[k];
		if(l==r)return;
		if(pos<=mid)modify(ls[k],l,mid,pos);
		else modify(rs[k],mid+1,r,pos);
	}
	int query(int k,int l,int r,int val){
		if(l==r)return l;
		int tmp=mid-l+1-sum[ls[k]];
		if(val<=tmp)return query(ls[k],l,mid,val);
		return query(rs[k],mid+1,r,val-tmp);
	}
	#undef mid
}seg;
int solve2(int x,int y){
	int pos=seg.query(rt[n+1],1,X,x); seg.modify(rt[n+1],1,X,pos);
	int ans=(pos<=n)?(pos*m):(v[n+1][pos-n-1]);
	v[n+1].push_back(y?y:ans); return ans;
}
int solve1(int x,int y){
	int pos=seg.query(rt[x],1,X,y); seg.modify(rt[x],1,X,pos);
	int ans=(pos<m)?((x-1)*m+pos):(v[x][pos-m]);
	v[x].push_back(solve2(x,ans)); return ans;
}
signed main(){
	scanf("%lld %lld %lld",&n,&m,&q); X=max(n,m)+q;
	while(q--){
		int x,y; scanf("%lld %lld",&x,&y);
		printf("%lld\n",y==m?solve2(x,0):solve1(x,y));
	}
	return 0;
}

评测结果