文件详细信息

下载本文件

本文件的大小为 1539 字节。

#include<cstdio>
#include<vector>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
typedef long long ll;
const int maxn=300000,maxm=300000,maxq=300000;
struct Seg{
	int sum,l,r;
}T[maxq*20];
int tot,rt[maxn+1],pos;
void modify(int&u,const int l,const int r){
	if(!u)T[u=++tot].sum=r-l+1;
	T[u].sum--;
	if(l==r)return;
	const int mid=(l+r)>>1;
	if(pos<=mid)modify(T[u].l,l,mid);
	else modify(T[u].r,mid+1,r);
}
int query(const int u,const int l,const int r){
	if(!u)return l+pos-1;
	const int mid=(l+r)>>1,tmp=T[u].l?T[T[u].l].sum:mid-l+1;
	if(pos<=tmp)return query(T[u].l,l,mid);
	else{
		pos-=tmp;
		return query(T[u].r,mid+1,r);
	}
}
int n,m,q;
std::vector<ll>v[maxn+1];
ll ans;
int main(){
	read(n),read(m),read(q);
	for(int i=1,x,y,loc;i<=q;i++){
		read(x),read(y);
		if(y!=m){
			pos=y;
			loc=query(rt[x],1,m+q-1);
			ans=loc<m?ll(x-1)*m+loc:v[x][loc-m];
			v[0].push_back(ans);
			pos=loc;
			modify(rt[x],1,m+q-1);
			pos=x;
			loc=query(rt[0],1,n+q);
			v[x].push_back(loc<=n?(ll)loc*m:v[0][loc-n-1]);
			pos=loc;
			modify(rt[0],1,n+q);
		}else{
			pos=x;
			loc=query(rt[0],1,n+q);
			ans=loc<=n?(ll)loc*m:v[0][loc-n-1];
			v[0].push_back(ans);
			pos=loc;
			modify(rt[0],1,n+q);
		}
		write(ans),putchar('\n');
	}
	return 0;
}