用一棵Splay按名次维护每个点，其中一个节点对应初始编号连续的一段区间，这样总节点数是$O(m)$的。
对每个编号记录这个点被Splay的那个节点维护，用std::map存储，只记录被修改的点。
每次删除时将一个点分裂成[l,k-1],k,[k+1,r]三个点（特判k=l或k=r），再删除k。
注意各种细节。
#include<map>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=;
int n,m,rt,nd,ans,op,x,y,L[N],R[N],len[N],f[N],ch[N][];
map<int,int>mp; int get(int l,int r){ nd++; L[nd]=l; R[nd]=r; len[nd]=r-l+; return nd; }
void upd(int x){ len[x]=len[ch[x][]]+len[ch[x][]]+R[x]-L[x]+; } void rot(int &rt,int x){
int y=f[x],z=f[y],w=ch[y][]==x;
if (rt==y) rt=x; else ch[z][ch[z][]==y]=x;
f[x]=z; f[y]=x; f[ch[x][w^]]=y;
ch[y][w]=ch[x][w^]; ch[x][w^]=y; upd(y);
} void splay(int &rt,int x){
while (x!=rt){
int y=f[x],z=f[y];
if (y!=rt) ((ch[z][]==y)^(ch[y][]==x)) ? rot(rt,x) : rot(rt,y);
rot(rt,x);
}
upd(x);
} int split(int x,int k){
int y=get(k+,R[x]); R[x]=k;
if (!ch[x][]) ch[x][]=y,f[y]=x;
else{
int s=ch[x][];
while (ch[s][]) s=ch[s][];
ch[s][]=y; f[y]=s;
}
splay(rt,y); mp[R[x]]=x; mp[R[y]]=y; return y;
} void Split(int &x,int k){
if (k<R[x]) split(x,k);
if (k>L[x]) x=split(x,k-);
splay(rt,x);
} void ins1(int x){
int s=rt;
while (ch[s][]) s=ch[s][];
ch[s][]=x; f[x]=s; splay(rt,x);
} void ins2(int x){
int s=rt;
while (ch[s][]) s=ch[s][];
ch[s][]=x; f[x]=s; splay(rt,x);
} void del(int x){
splay(rt,x);
int ls=ch[x][],rs=ch[x][];
f[ls]=f[rs]=; ch[x][]=ch[x][]=;
if (!ls || !rs) { rt=ls+rs; return; }
int s=ls; while (ch[s][]) s=ch[s][];
splay(ls,s); ch[s][]=rs; f[rs]=rt=s; upd(s);
} int find(int k){
for (int x=rt; ; ){
if (k<=len[ch[x][]]) x=ch[x][];
else{
k-=len[ch[x][]];
if (k<=R[x]-L[x]+) return k+L[x]-;
else k-=R[x]-L[x]+,x=ch[x][];
}
}
} int main(){
freopen("bzoj3595.in","r",stdin);
freopen("bzoj3595.out","w",stdout);
scanf("%d%d",&n,&m); rt=get(,n); mp[n]=;
rep(i,,m){
scanf("%d%d",&op,&x); x-=ans;
if (op==){
scanf("%d",&y); y-=ans;
int t=mp.lower_bound(x)->second;
Split(t,x); printf("%d\n",ans=len[t]-len[ch[t][]]);
L[t]=R[t]=y; mp[y]=t;
}
if (op==){
int t=mp.lower_bound(x)->second;
Split(t,x); printf("%d\n",ans=len[t]-len[ch[t][]]);
del(t); ins1(t);
}
if (op==){
int t=mp.lower_bound(x)->second;
Split(t,x); printf("%d\n",ans=len[t]-len[ch[t][]]);
del(t); ins2(t);
}
if (op==) printf("%d\n",ans=find(x));
}
return ;
}