rt

https://www.luogu.com.cn/record/38182222

WA成45pts

高度怀疑split操作写错了，感觉是询问最后一列的人出错了

#include<stdio.h>
#include<bits/stdc++.h>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;

const int N=3e5+5;
int n,m,q,x,y,tot,top;
int T[N],s[N];
struct node{int ch[2],fa;long long l,r,size;}t[N<<5];

inline int newnode(void)
{
	return top>0?s[top--]:++tot;
}

inline void pushup(int x)
{
	t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].r-t[x].l+1;
}

inline void rotate(int x)
{
	int y=t[x].fa,z=t[y].fa,k=(x==t[y].ch[1]);
	t[z].ch[y==t[z].ch[1]]=x,t[x].fa=z;
	t[y].ch[k]=t[x].ch[!k],t[t[x].ch[!k]].fa=y;
	t[x].ch[!k]=y,t[y].fa=x;
	pushup(y),pushup(x);
}

inline void splay(int &root,int x,int to)
{
	while(t[x].fa!=to)
	{
		int y=t[x].fa,z=t[y].fa;
		if(z!=to) rotate((x==t[y].ch[1])^(y==t[z].ch[1])?x:y);
		rotate(x);
	}
	if(!to) root=x;
}

inline void insert(int &root,long long l,long long r)
{
	if(!root)
	{
		root=newnode();
		t[root]=(node){{0,0},0,l,r,r-l+1};
		return;
	}
	int u=root,fa=0;
	while(u) fa=u,u=t[u].ch[1];
	u=newnode();
	t[fa].ch[1]=u;
	t[u]=(node){{0,0},fa,l,r,r-l+1};
	splay(root,u,0);
}

inline int next(int &root,int u,bool k)
{
	splay(root,u,0);
	u=t[u].ch[k];
	if(!u) return 0;
	while(t[u].ch[!k]) u=t[u].ch[!k];
	return u;
}

inline void split(int &root,int u,long long k)
{
	int l=0,r=0;
	if(k!=t[u].l) t[l=newnode()]=(node){{0,0},0,t[u].l,k-1,k-t[u].l};
	if(k!=t[u].r) t[r=newnode()]=(node){{0,0},0,k+1,t[u].r,t[u].r-k};
	s[++top]=u;
	int pre=next(root,u,0),nex=next(root,u,1);
	if(!pre&&!nex)
		if(l&&r) root=l,t[l].ch[1]=r,t[r].fa=l,pushup(l);
		else root=max(l,r);
	else if(nex&&pre)
	{
		splay(root,pre,0),splay(root,nex,pre);
		if(l&&r) t[nex].ch[0]=l,t[l].fa=nex,t[l].ch[1]=r,t[r].fa=l,splay(root,r,0);
		else t[nex].ch[0]=max(l,r),t[max(l,r)].fa=nex,pushup(nex),pushup(pre);
	}
	else if(pre)
	{
		splay(root,pre,0);
		if(l&&r) t[pre].ch[1]=l,t[l].fa=pre,t[l].ch[1]=r,t[r].fa=l,splay(root,r,0);
		else t[pre].ch[1]=max(l,r),t[max(l,r)].fa=pre,pushup(pre);
	}
	else
	{
		splay(root,nex,0);
		if(l&&r) t[nex].ch[0]=l,t[l].fa=nex,t[l].ch[1]=r,t[r].fa=l,splay(root,r,0);
		else t[nex].ch[0]=max(l,r),t[max(l,r)].fa=nex,pushup(nex);
	}
	insert(T[n+1],k,k);
}

inline long long kth(int &root,long long k)
{
	int u=root;
	long long ans=0;
	while(true)
		if(t[t[u].ch[0]].size>=k) u=t[u].ch[0];
		else if(k>t[t[u].ch[0]].size+t[u].r-t[u].l+1) k-=t[t[u].ch[0]].size+t[u].r-t[u].l+1,u=t[u].ch[1];
		else
		{
			ans=t[u].l+k-t[t[u].ch[0]].size-1;
			split(root,u,ans);
			return ans;
		}
}

int main(void)
{
	scanf("%d%d%d",&n,&m,&q);
	for(register int i=1;i<=n;++i)
		insert(T[i],1ll*(i-1)*m+1,1ll*i*m-1);
	for(register int i=1;i<=n;++i)
		insert(T[n+1],1ll*i*m,1ll*i*m);
	while(q--)
	{
		scanf("%d%d",&x,&y);
		printf("%lld\n",y==m?kth(T[n+1],x):kth(T[x],y));
		if(y!=m)
		{
			long long k=kth(T[n+1],x);
			insert(T[x],k,k);
		}
	}
	return 0;
}