splay缩点。
#include<cstdio>
#define M (i+j>>1)
const int N=20005;
typedef struct node*ptr;
struct node{
ptr i,j;int l,r,s;
int foo(){return i->s+r-l+1;}
ptr up(){
s=foo()+j->s;return this;
}
}e[N*6];
ptr a=e;
ptr pre(int*z,int i,int j){
if(i>j)return e;
node s={pre(z,i,M-1),pre(z,M+1,j),z[M],z[M]};
return(*++a=s).up();
}
void zig(ptr&o,ptr&s){ptr t=o->i;o->i=s,s=o->up(),o=t;}
void zag(ptr&o,ptr&s){ptr t=o->j;o->j=s,s=o->up(),o=t;}
ptr splay(int z,ptr&o){
ptr s=e,t=e;
while(1)
if(z<=o->i->s){
if(z<=o->i->i->s)zig(o,o->i->j);
zig(o,s);
}else if(z>o->foo()){
z-=o->foo();
if(z>o->j->foo())
z-=o->j->foo(),zag(o,o->j->i);
zag(o,t);
}else{
z+=o->l-o->i->s-1;
if(o->l!=z)
o->i=(*++a=(node){o->i,e,o->l,z-1}).up(),o->l=z;
if(o->r!=z)
o->j=(*++a=(node){e,o->j,z+1,o->r}).up(),o->r=z;
break;
}
while(s!=e)zig(s,o->j);
while(t!=e)zag(t,o->i);
return o->up();
}
ptr&splay(int s,int t,ptr&r){
splay(s,r);
return splay(t-s+2,r->j)->i;
}
int main(){
int n,m,c,p,s,t;
static int z[N];
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",z+i);
ptr r=pre(z,0,n+1);
while(m--){
scanf("%d%d",&c,&p);
if(c==2)
printf("%d\n",splay(p+1,r)->l);
else{
scanf("%d",&s);
if(c==1)splay(p,s,r)=e;
else{
scanf("%d",&t);
splay(p+1,p,r)=(*++a=(node){e,e,s,t}).up();
}
}
}
}
