记录编号	477615	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2017]列队	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	3.713 s
提交时间	2017-12-05 11:34:48	内存使用	274.95 MiB

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char cc;inline void R_int(int &x){
	while(cc=getchar(),cc<'!');x=cc-48;
	while(cc=getchar(),cc>'!')x=x*10+cc-48;	
}
#define LL long long
const int maxn=300005<<1,SIZEN=maxn*20;
int n,m,Q,cnt=0,pos,rx[SIZEN],ls[SIZEN],rs[SIZEN],v[SIZEN];
LL qx,ans,num[SIZEN];
int Set(int l,int r){
	if(l>n)return 0;int rt=++cnt;
	if(l==r){num[rt]=l*1ll*m;return rt;}
	int mid=(l+r)>>1;
	ls[rt]=Set(l,mid),rs[rt]=Set(mid+1,r);
	return rt;
}
void Del(int &rt,int l,int r){
	if(!rt)rt=++cnt;
	if(l==r){
		if(!num[rt])ans=-l;else ans=num[rt];
		v[rt]=1;return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid-v[ls[rt]])Del(ls[rt],l,mid);
	else pos+=v[ls[rt]],Del(rs[rt],mid+1,r);
	v[rt]=v[ls[rt]]+v[rs[rt]];
}
LL Del(int x){
	Del(rx[x],1,maxn);
	if(ans<0)return (x-1)*1ll*m-ans;
	return ans;
}
void Add(int &rt,int l,int r){
	if(!rt)rt=++cnt;
	if(l==r){num[rt]=qx;return;}
	int mid=(l+r)>>1;
	if(pos<=mid-v[ls[rt]])Add(ls[rt],l,mid);
	else pos+=v[ls[rt]],Add(rs[rt],mid+1,r);
}
void Run(int x,int y){
	pos=x,qx=Del(0);
	if(y^m)pos=m,Add(rx[x],1,maxn),pos=y,qx=Del(x);
	pos=n,Add(rx[0],1,maxn),printf("%lld\n",qx);
}
int main(){
	freopen("2017phalanx.in","r",stdin);freopen("2017phalanx.out","w",stdout);
	int x,y;R_int(n),R_int(m),R_int(Q);rx[0]=Set(1,maxn);
	while(Q--)R_int(x),R_int(y),Run(x,y);
}