LOJ提交记录

萌新的代码，luogu全WA，感谢各位路过的大佬

把快读去掉换成scanf，还是WA。

Code:

#include<bits/stdc++.h>
#define maxn 300005
#define rg register
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
long long n,m;
int root[maxn],cnt;
struct yyy{
	int ls,rs,size,rnd;
	long long l,r;
}a[maxn*10];
inline int qlen(int k){
	if (!k) return 0;
	return a[k].r-a[k].l+1;
}
inline void Pushup(int k){
	a[k].size=a[a[k].ls].size+a[a[k].rs].size+qlen(k);
}
inline void split(int k,int x,int &a_,int &b_){
	if (!k) a_=b_=0;
	else{
		if (a[a[k].ls].size+qlen(k)<x) a_=k,split(a[k].rs,x-a[a[k].ls].size-qlen(k),a[k].rs,b_);
		else b_=k,split(a[k].ls,x,a_,a[k].ls);
		Pushup(k);
	}
}
inline int merge(int u,int v){
	if (!u||!v) return u|v;
	if (a[u].rnd<a[v].rnd){
		a[u].rs=merge(a[u].rs,v);
		Pushup(u);return u;
	}
	else{
		a[v].ls=merge(u,a[v].ls);
		Pushup(v);return v;
	}
}
inline int clone(long long val){
	a[++cnt].l=a[cnt].r=val;a[cnt].rnd=rand();a[cnt].size=1;
	return cnt;
}
inline int Build(long long l,long long r){
	if (l==r) return clone(l*m);
	long long mid=l+r>>1;return merge(Build(l,mid),Build(mid+1,r));
}
inline int at(int k){
	int x=1;
	while (k){
		if (x<=a[a[k].ls].size) k=a[k].ls;
		else if (x<=a[a[k].ls].size+qlen(k)) return k;
		else k=a[k].rs;
	}
}
inline void print(int k){
	if (a[k].ls) print(a[k].ls);
	printf(" %lld~%lld ",a[k].l,a[k].r);
	if (a[k].rs) print(a[k].rs);
}
int main(){
	//freopen("P3960_1.in","r",stdin);
	//freopen("my.out","w",stdout);
	rg int i,q,tmp1,tmp2,tmp3,tmp4,tmp5,tmp6,k1,k2,x,y,k;
	rg long long tot;
	srand(time(0));
	scanf("%lld%lld",&n,&m);read(q);
	root[n+1]=Build(1,n);
	for (i=1;i<=n;i++){
		root[i]=++cnt;
		a[cnt].l=(i-1)*m+1;
		a[cnt].r=i*m-1;
		a[cnt].rnd=rand();
		a[cnt].size=m-1;
	}
//	for (i=1;i<=n+1;i++,putchar('\n')) print(root[i]);
	while (q--){
		read(x);read(y);
		if (y==m){
			split(root[n+1],x,tmp1,tmp2);
			split(tmp2,2,tmp2,tmp3);
			printf("%lld\n",a[tmp2].l);
			root[n+1]=merge(tmp1,merge(tmp3,tmp2));
		}
		else{
			k1=k2=0;
			split(root[x],y,tmp1,tmp2);k=at(tmp2);
			split(tmp2,qlen(k)+1,tmp2,tmp3);tot=a[tmp2].l-1+y-a[tmp1].size;
			printf("%lld\n",tot);
			if (tot^a[tmp2].l) a[++cnt].l=a[tmp2].l,a[cnt].r=tot-1,a[cnt].rnd=rand(),a[cnt].size=qlen(cnt),k1=cnt;
			if (tot^a[tmp2].r) a[++cnt].l=tot+1,a[cnt].r=a[tmp2].r,a[cnt].rnd=rand(),a[cnt].size=qlen(cnt),k2=cnt;
			a[tmp2].l=a[tmp2].r=tot;a[tmp2].size=1;
			split(root[n+1],x,tmp4,tmp5);
			split(tmp5,2,tmp5,tmp6);
			root[n+1]=merge(tmp4,merge(tmp6,tmp2));
			root[x]=merge(merge(tmp1,k1),merge(k2,merge(tmp3,tmp5)));
		}
//		for (i=1;i<=n+1;i++,putchar('\n')) print(root[i]);
	}
	return 0;
}