https://www.luogu.org/problemnew/show/P3960
常数超大的treap
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
#define N 6001000
queue<int> q;
int ch[N][],r[N],mem;
ll lx[N],rx[N],sz[N];
int rand1()
{
static int x=;
return x=(48271LL*x+)%;
}
int getnode()
{
int t=q.front();q.pop();r[t]=rand1();
lx[t]=rx[t]=sz[t]=ch[t][]=ch[t][]=;
return t;
}
void delnode(int x) {q.push(x);}
void upd(int x) {sz[x]=sz[ch[x][]]+sz[ch[x][]]+rx[x]-lx[x]+;}
int merge(int a,int b)
{
if(!a||!b) return a+b;
if(r[a]<r[b])
{
ch[a][]=merge(ch[a][],b);upd(a);
return a;
}
else
{
ch[b][]=merge(a,ch[b][]);upd(b);
return b;
}
}
pi split(int a,ll n)
{
if(!a) return mp(,);
ll ls=sz[ch[a][]];pi t;
if(n<=ls)
{
t=split(ch[a][],n);ch[a][]=t.se;
upd(a);t.se=a;
}
else
{
t=split(ch[a][],n-ls-(rx[a]-lx[a]+));ch[a][]=t.fi;
upd(a);t.fi=a;
}
return t;
}
int split_node(int a,ll n)
{
ll ls=sz[ch[a][]];
if(n<=ls) {ch[a][]=split_node(ch[a][],n);return a;}
else if(n<=ls+rx[a]-lx[a]+)
{
n-=ls;
int now=ch[a][],rc=ch[a][],t;ll l=lx[a],r=rx[a];
if(n!=)
{
t=getnode();lx[t]=l;rx[t]=l+n-;upd(t);
now=merge(now,t);
}
t=getnode();lx[t]=rx[t]=l+n-;upd(t);
now=merge(now,t);
if(n!=r-l+)
{
t=getnode();lx[t]=l+n;rx[t]=r;upd(t);
now=merge(now,t);
}
now=merge(now,rc);delnode(a);
return now;
}
else {ch[a][]=split_node(ch[a][],n-(ls+rx[a]-lx[a]+));return a;}
}
int rt[];
ll n,m;int qq;
int main()
{
int i,t;ll x,y,ans;pi p1,p2,p3,p4;
for(i=;i<N;++i) q.push(i);
scanf("%lld%lld%d",&n,&m,&qq);
for(i=;i<=n;i++)
{
t=getnode();lx[t]=ll(i-)*m+;rx[t]=ll(i)*m-;upd(t);
rt[i]=t;
}
for(i=;i<=n;i++)
{
t=getnode();lx[t]=rx[t]=i*m;upd(t);
rt[]=merge(rt[],t);
}
while(qq--)
{
scanf("%lld%lld",&x,&y);
if(y==m)
{
rt[]=split_node(rt[],x);
p1=split(rt[],x-);p2=split(p1.se,);
ans=lx[p2.fi];
rt[]=merge(p1.fi,merge(p2.se,p2.fi));
}
else
{
rt[x]=split_node(rt[x],y);
p1=split(rt[x],y-);p2=split(p1.se,);
ans=lx[p2.fi];
rt[x]=merge(p1.fi,p2.se);
rt[]=split_node(rt[],x);
p3=split(rt[],x-);p4=split(p3.se,);
rt[x]=merge(rt[x],p4.fi);
rt[]=merge(p3.fi,merge(p4.se,p2.fi));
}
printf("%lld\n",ans);
}
return ;
}