看到区间翻转果断Splay。

然后就没了...

设当前光标位置\(p\)。

MOVE,PREV,NEXT只需要加减\(p\)就好了。

设\(f_x\)为Splay中第\(x\)小的节点的编号。

INSERT可以将Splay中\(f_p\)splay到根,\(f_{p+1}\)splay到根的儿子。

把新的节点先建一棵Splay,新Splay的根连接在\(f_{p+1}\)的左儿子上。

DELETE可以将\(f_p\)splay到根,\(f_{p+n+1}\)splay到根的儿子,删除\(f_{p+n+1}\)的左儿子即可。

ROTATE将\(f_p\)splay到根,\(f_{p+n+1}\)splay到根的儿子,改变\(f_{p+n+1}\)的左儿子的翻转标记即可。

GET直接输出\(f_{p+1}\)的值。

没了。

code:

#include
    
     #define lc(x) t[x].c[0]#define rc(x) t[x].c[1]using namespace std;struct node{    int c[2],f,sz,tag;    char v;}t[(1<<21)+10];int n,m,p,rt,trt,cnt=2;char op[10],s[(1<<21)+10],tmp;void Upd(int x){    t[x].sz=t[lc(x)].sz+t[rc(x)].sz+1;}void Psd(int x){    t[x].tag?swap(lc(x),rc(x)),(lc(x)?t[lc(x)].tag^=1:0),(rc(x)?t[rc(x)].tag^=1:0),t[x].tag=0:0;}void Rotate(int x){    int y=t[x].f,z=t[y].f;    Psd(y),Psd(x);    int c=rc(y)==x,gc=rc(z)==y;    z?t[z].c[gc]=x:0,t[x].f=z;    t[y].c[c]=t[x].c[c^1],t[t[x].c[c^1]].f=y;    t[x].c[c^1]=y,t[y].f=x;    Upd(y),Upd(x);}void Splay(int x,int f){    while(t[x].f!=f){        int y=t[x].f,z=t[y].f;        Psd(z),Psd(y);        if(z==f)Rotate(x);        else if((rc(y)==x)==(rc(z)==y))Rotate(y),Rotate(x);        else Rotate(x),Rotate(x);    }    if(!f)rt=x;}int Find(int x){    ++x;    int nw=rt;    while(nw){        Psd(nw);        if(t[lc(nw)].sz>=x)nw=lc(nw);        else if(t[lc(nw)].sz+1==x)return(Splay(nw,0),nw);        else x-=t[lc(nw)].sz+1,nw=rc(nw);    }}void Build(int l,int r,int &lst,int f){    int mid=l+r>>1;    lst=++cnt,t[cnt].f=f,t[cnt].v=s[mid],t[cnt].sz=1;    l
     
      mid?Build(mid+1,r,rc(lst),lst),0:0;    Upd(lst);}void Insert(int x,int len){    Build(1,len,trt,0);    if(!rt)rt=trt;    int l=Find(x),r=Find(x+1);    Splay(l,0),Splay(r,l);    lc(r)=trt,t[trt].f=r;    Upd(r),Upd(l);}void Delete(int x,int len){    int l=Find(x),r=Find(x+len+1);    Splay(l,0),Splay(r,l);    t[lc(r)].f=0,lc(r)=0;    Upd(r),Upd(l);}void Reverse(int x,int len){    int l=Find(x),r=Find(x+len+1);    Splay(l,0),Splay(r,l);    t[lc(r)].tag^=1;}int main(){    scanf("%d",&n);    t[1].c[1]=t[1].sz=2,rt=t[2].f=t[2].sz=1;    while(n--){        scanf("%s",op+1);        if(op[1]=='M')scanf("%d",&m),p=m;        else if(op[1]=='I'){            scanf("%d",&m),getchar();            for(int i=1;i<=m;++i)s[i]=getchar();            Insert(p,m);        }else if(op[1]=='D')scanf("%d",&m),Delete(p,m);        else if(op[1]=='R')scanf("%d",&m),Reverse(p,m);        else if(op[1]=='G')tmp=t[Find(p+1)].v,tmp!='\n'?putchar(tmp):0,putchar('\n');        else if(op[1]=='P')--p;        else if(op[1]=='N')++p;    }    return 0;}