代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,q,a[300010][2],r[300010],t[300010],size,s[10000010][2],st[100],OnF;
long long m,num[10000010],c[10000010];
char BuF[1<<26],*InF=BuF,WuF[1<<26];
template<typename T>void read(T &x){
	for(;*InF<33;++InF);
	for(x=0;32<*InF;x=(x<<3)+(x<<1)+(*InF++^48));
}
template<typename T>void write(T x){
    for(st[0]=0;x;x/=10){
        st[++st[0]]=x%10+48;
    }
    for(;st[0];WuF[OnF++]=st[st[0]--]);
    WuF[OnF++]='\n'; 
}
void add(int p,int x,long long y,int l,int r,int h){
	if(l==r){
		num[p]=y;
		c[p]=1;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=x){
		if(!s[p][0]){
			s[p][0]=++size;
		}
		add(s[p][0],x,y,l,mid,h);
	}else{
		if(!s[p][1]){
			s[p][1]=++size;
		}
		add(s[p][1],x,y,mid+1,r,h);
	}
	c[p]=(s[p][0]?c[s[p][0]]:max(min(mid,t[h])-l+1,0))+(s[p][1]?c[s[p][1]]:max(min(r,t[h])-mid,0));
}
long long del(int p,int x,int l,int r,int h){
	if(l==r){
		if(!num[p]){
			num[p]=h?(h-1)*m+l:l*m;
		}
		c[p]=0;
		return(num[p]);
	}
	int mid=(l+r)>>1,ls;
    long long re;
	if((ls=(s[p][0]?c[s[p][0]]:mid-l+1))>=x){
		if(!s[p][0]){
			s[p][0]=++size;
		}
		re=del(s[p][0],x,l,mid,h);
	}else{
		if(!s[p][1]){
			s[p][1]=++size;
		}
		re=del(s[p][1],x-ls,mid+1,r,h);
	}
	c[p]=(s[p][0]?c[s[p][0]]:max(min(mid,t[h])-l+1,0))+(s[p][1]?c[s[p][1]]:max(min(r,t[h])-mid,0));
	return(re);
}
int main(){
	fread(BuF,1,1<<26,stdin);
	read(n);read(m);read(q);
	size=t[0]=n;
	for(int i=1;i<=n;++i){
		r[i]=t[i]=m-1;
	}
	for(int i=1;i<=q;++i){
		read(a[i][0]);read(a[i][1]);
		++r[a[i][0]];
	}
	for(int i=1;i<=q;++i){
	    long long num;
	    if(a[i][1]<m){
    		num=del(a[i][0],a[i][1],1,r[a[i][0]],a[i][0]);
    		add(a[i][0],++t[a[i][0]],del(0,a[i][0],1,n+q,0),1,r[a[i][0]],a[i][0]);
    		add(0,++t[0],num,1,n+q,0);
    	}else{
    	    add(0,++t[0],num=del(0,a[i][0],1,n+q,0),1,n+q,0);
        }
        write(num);
	}
	fwrite(WuF,1,OnF,stdout);
	fclose(stdin);
	fclose(stdout);
	return(0);
}

评测结果