emm改掉了一个很显然的错误，现在是70分
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<map>
#define ls t[x].son[0]
#define rs t[x].son[1]
#define test print(root),cerr<<endl;
using namespace std;
const int maxn=5e5+10,inf=0x3f3f3f3f;
int n,m,root,tot,ans;
struct node
{
int size,fa,l,r;
int son[2];
}t[maxn];
map<int,int>map1;
int read()
{
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return f*x;
}
void update(int x)
{
t[x].size=t[ls].size+t[rs].size+t[x].r-t[x].l+1;
}
void rotate(int x)
{
int y=t[x].fa;
int z=t[y].fa;
int k=t[y].son[1]==x;
t[z].son[t[z].son[1]==y]=x,t[x].fa=z;
t[t[x].son[k^1]].fa=y,t[y].son[k]=t[x].son[k^1];
t[x].son[k^1]=y,t[y].fa=x;
update(y),update(x);
}
void splay(int x,int to)
{
while(t[x].fa!=to)
{
int y=t[x].fa;
int z=t[y].fa;
if(z!=to)(t[y].son[1]==x)^(t[z].son[1]==y)?rotate(x):rotate(y);
rotate(x);
}
if(to==0)root=x;
}
int find_kth(int x)
{
int now=root;
while(true)
{
int sum=t[t[now].son[0]].size+t[now].r-t[now].l+1;
if(x>sum)
{
x-=sum;
now=t[now].son[1];
}
else if(t[t[now].son[0]].size>=x)now=t[now].son[0];
else
{
x-=t[t[now].son[0]].size;
return x+t[now].l-1;
}
}
}
void split(int x,int id)
{
if(t[x].l==t[x].r)return;
else if(t[x].l==id)
{
int now=++tot;
map1[id]=x,map1[t[x].r]=now;
t[now].son[1]=t[x].son[1];
t[t[x].son[1]].fa=now;
t[x].son[1]=now;
t[now].fa=x;
t[now].l=t[x].l+1,t[now].r=t[x].r;
t[x].l=t[x].r=id;
update(rs),update(x);
return;
}
else if(t[x].r==id)
{
int now=++tot;
map1[id]=x,map1[t[x].r-1]=now;
t[now].son[0]=t[x].son[0];
t[t[x].son[0]].fa=now;
t[x].son[0]=now;
t[now].fa=x;
t[now].l=t[x].l,t[now].r=t[x].r-1;
t[x].l=t[x].r=id;
update(ls),update(x);
return;
}
else
{
int lnow=++tot;
int rnow=++tot;
map1[id]=x,map1[id-1]=lnow,map1[t[x].r]=rnow;
t[lnow].son[0]=t[x].son[0];
t[rnow].son[1]=t[x].son[1];
t[t[x].son[0]].fa=lnow;
t[t[x].son[1]].fa=rnow;
t[lnow].fa=t[rnow].fa=x;
t[x].son[0]=lnow;t[x].son[1]=rnow;
t[lnow].l=t[x].l,t[lnow].r=id-1;
t[rnow].l=id+1,t[rnow].r=t[x].r;
t[x].l=t[x].r=id;
update(ls),update(rs),update(x);
return;
}
}
void init()
{
root=++tot;
t[root].l=1;
t[root].r=n;
t[root].size=n;
map1[n]=1;
}
void print(int x)
{
if(ls)print(ls);
if(t[x].l==t[x].r)cerr<<t[x].l<<" ";
else cerr<<t[x].l<<" "<<t[x].r<<" ";
// cerr<<t[ls].l<<" "<<t[ls].r<<" "<<t[rs].l<<" "<<t[rs].r<<" "<<t[t[x].fa].l<<" "<<t[t[x].fa].r<<endl;
if(rs)print(rs);
}
int main()
{
n=read();m=read();
init();
for(int i=1;i<=m;i++)
{
int op=0,x=0,y=0;
op=read();x=read();
if(op==1)
{
y=read();
x-=ans,y-=ans;
int k=map1.lower_bound(x)->second;
split(k,x);
splay(k,0);
ans=t[t[root].son[0]].size+1;
t[root].l=t[root].r=y;
map1[y]=k;
map1[x]=0;
printf("%d\n",ans);
// test
}
else if(op==2)
{
x-=ans;
int k=map1.lower_bound(x)->second;
split(k,x);
splay(k,0);
//test
ans=t[t[root].son[0]].size+1;
int now=t[root].son[1];
while(t[now].son[0])now=t[now].son[0];
splay(now,root);
if(t[root].son[0])
{
t[t[root].son[0]].fa=t[root].son[1];
t[t[root].son[1]].son[0]=t[root].son[0];
t[root].son[0]=0;
update(t[root].son[1]),update(root);
}
printf("%d\n",ans);
// test
}
else if(op==3)
{
x-=ans;
int k=map1.lower_bound(x)->second;
split(k,x);
splay(k,0);
ans=t[t[root].son[0]].size+1;
int now=t[root].son[0];
while(t[now].son[1])now=t[now].son[1];
splay(now,root);
if(t[root].son[1])
{
t[t[root].son[1]].fa=t[root].son[0];
t[t[root].son[0]].son[1]=t[root].son[1];
t[root].son[1]=0;
update(t[root].son[0]),update(root);
}
printf("%d\n",ans);
// test
}
else
{
x-=ans;
ans=find_kth(x);
printf("%d\n",ans);
}
}
return 0;
}
```
by ysj1173886760 @ 2018-09-01 11:39:18
求第二组数据
by ysj1173886760 @ 2018-09-01 12:24:48