传送门
题意简述：
给一个有优先级的nnn个人的序列，初始的时候第iii个人排名为iii，现在有mmm个操作，种类如下：
- 把编号为xxx的改成yyy，输出改前xxx的排名
- 把编号为xxx放到队首，输出改前xxx的排名
- 把编号为xxx放到队尾，输出改前xxx的排名
- 输出排名为xxx的编号。
强制在线，n≤1e8,m≤1e5n\le1e8,m\le1e5n≤1e8,m≤1e5
思路：
本蒟蒻的第一道splay!splay!splay!过了好激动qwqqwqqwq
由于nnn较大直接上平衡树ttt飞，考虑到操作数少，如果我们把未修改的段压成一个点然后用splaysplaysplay维护，每次就只会最多把一个分成333个，最终节点数只有3e53e53e5个就可以过了，于是用setsetset和mapmapmap辅助维护一下即可。
注意细节。
然而博主的常数太大bzoj过不了，实测1s能跑过
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
const int N=3e5+5;
typedef pair<int,int> pii;
map<pii,int>S;
map<int,int>mp,imp;
set<int>upd;
typedef set<int>::iterator It;
int n,m,tt=1;
namespace Splay{
#define lc (son[p][0])
#define rc (son[p][1])
int tot=0,rt=0,fa[N],son[N][2],L[N],R[N],siz[N],sum[N];
inline int which(const int&x){return x==son[fa[x]][1];}
inline void pushup(int p){siz[p]=siz[lc]+1+siz[rc],sum[p]=sum[lc]+(R[p]-L[p]+1)+sum[rc];}
inline int build(int l,int r,int ft,int t){
fa[++tot]=ft,ft?son[ft][t]=tot:0;
son[tot][0]=son[tot][1]=0,S[pii(l,r)]=tot;
siz[tot]=1,sum[tot]=(R[tot]=r)-(L[tot]=l)+1;
return tot;
}
inline void rotate(int x){
int y=fa[x],z=fa[y],t=which(x);
if(z)son[z][which(y)]=x;
fa[x]=z,fa[y]=x,son[y][t]=son[x][t^1],son[x][t^1]=y;
if(son[y][t])fa[son[y][t]]=y;
pushup(y),pushup(x);
}
inline void splay(int x,int ff=0){
while(fa[x]!=ff){
if(fa[fa[x]]!=ff)rotate(which(x)==which(fa[x])?fa[x]:x);
rotate(x);
}
if(!ff)rt=x;
}
inline void insert(int l,int r,int k){
--k;
int p=rt,ft=0,t;
while(p){
ft=p;
if(siz[lc]>=k)p=lc,t=0;
else k-=siz[lc]+1,p=rc,t=1;
}
splay(build(l,r,ft,t));
}
inline int pre(int p){
splay(p),p=lc;
while(rc)p=rc;
return splay(p),p;
}
inline int suf(int p){
splay(p),p=rc;
while(lc)p=lc;
return splay(p),p;
}
inline void delet(int p){
int pr=pre(p),su=suf(p);
splay(pr),splay(su,pr),son[su][0]=0,splay(su);
}
inline void init(){
insert(0,0,1),insert(1,n,2),insert(n+1,n+1,3);
upd.insert(0),upd.insert(n+1);
}
inline int update(int x,int y){
int l,r,t=mp[x]?mp[x]:x,p,ret;
mp[y]=mp[x]?mp[x]:x,imp[mp[y]]=y,mp.erase(x);
It ir=upd.lower_bound(t),il;
if(*ir==t)splay(p=S[pii(t,t)]),ret=sum[lc];
else{
il=ir;
while(*ir<t)++ir;
while(*il>t)--il;
l=*il+1,r=*ir-1;
splay(p=S[pii(l,r)]),ret=sum[lc]+t-l;
}
return ret;
}
inline int Pre(int x){
int l,r,t=mp[x]?mp[x]:x,p,ret,rk;
It ir=upd.lower_bound(t),il;
if(*ir==t){
splay(p=S[pii(t,t)]),ret=sum[lc];
delet(p),insert(t,t,2);
}
else{
il=ir;
while(*ir<t)++ir;
while(*il>t)--il;
l=*il+1,r=*ir-1,splay(p=S[pii(l,r)]),ret=sum[lc]+t-l,rk=siz[lc]+1;
upd.insert(t);
delet(p);
if(t==l)insert(t+1,r,rk);
else if(t==r)insert(l,t-1,rk);
else insert(l,t-1,rk),insert(t+1,r,rk+1);
insert(t,t,2);
}
return ret;
}
inline int Suf(int x){
int l,r,t=mp[x]?mp[x]:x,p,ret,rk;
It ir=upd.lower_bound(t),il;
if(*ir==t){
splay(p=S[pii(t,t)]),ret=sum[lc];
delet(p),insert(t,t,siz[rt]);
}
else{
il=ir;
while(*ir<t)++ir;
while(*il>t)--il;
l=*il+1,r=*ir-1,splay(p=S[pii(l,r)]),ret=sum[lc]+t-l,rk=siz[lc]+1;
upd.insert(t);
delet(p);
if(t==l)insert(t+1,r,rk);
else if(t==r)insert(l,t-1,rk);
else insert(l,t-1,rk),insert(t+1,r,rk+1);
insert(t,t,siz[rt]);
}
return ret;
}
inline int Rank(int k){
++k;
int p=rt,ret;
while(p){
if(sum[lc]>=k)p=lc;
else if(sum[lc]+R[p]-L[p]+1>=k){
ret=L[p]+(k-sum[lc])-1;
break;
}
else k-=sum[lc]+R[p]-L[p]+1,p=rc;
}
return !imp[ret]?ret:imp[ret];
}
#undef lc
#undef rc
}
int main(){
n=read(),m=read();
Splay::init();
for(ri x,y,lastans=0,op;m;--m,++tt){
op=read();
switch(op){
case 1:{x=read()-lastans,y=read()-lastans,lastans=Splay::update(x,y);break;}
case 2:{x=read()-lastans,lastans=Splay::Pre(x);break;}
case 3:{x=read()-lastans,lastans=Splay::Suf(x);break;}
case 4:{x=read()-lastans,lastans=Splay::Rank(x);break;}
}
cout<<lastans<<'\n';
}
return 0;
}