思路
FHQ Treap的板子
用FHQ Treap维护中序遍历序列即可
然后数组开够！
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node{
int lson,rson,sz,num,ran;
}FHQ[300000*30];
int nowpos,n,m,Nodecnt,a[300000*30],root;
int new_Node(int num){
++Nodecnt;
FHQ[Nodecnt].lson=FHQ[Nodecnt].rson=0;
FHQ[Nodecnt].ran=rand();
FHQ[Nodecnt].num=num;
FHQ[Nodecnt].sz=1;
return Nodecnt;
}
void pushup(int o){
FHQ[o].sz=FHQ[FHQ[o].lson].sz+FHQ[FHQ[o].rson].sz+1;
}
void split(int val,int now,int &x,int &y){//sz
if(!now){
x=y=0;
return;
}
if(val<=FHQ[FHQ[now].lson].sz){
y=now;
split(val,FHQ[now].lson,x,FHQ[now].lson);
}
else{
x=now;
split(val-FHQ[FHQ[now].lson].sz-1,FHQ[now].rson,FHQ[now].rson,y);
}
pushup(now);
}
int merge(int x,int y){//x.w<y.w
if(x*y==0)
return x+y;
if(FHQ[x].ran<FHQ[y].ran){
FHQ[x].rson=merge(FHQ[x].rson,y);
pushup(x);
return x;
}
else{
FHQ[y].lson=merge(x,FHQ[y].lson);
pushup(y);
return y;
}
}
int build(int l,int r){
if(l>r)
return 0;
int mid=(l+r)>>1;
int t=new_Node(a[mid]);
FHQ[t].lson=build(l,mid-1);
FHQ[t].rson=build(mid+1,r);
pushup(t);
return t;
}
void query(int o){
if(!o)
return;
query(FHQ[o].lson);
printf("%c",FHQ[o].num);
query(FHQ[o].rson);
}
char opt[20];
int main(){
root=new_Node(-1);
nowpos=1;
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%s",opt);
if(opt[0]=='M'){
int x;
scanf("%d",&x);
nowpos=x+1;
}
else if(opt[0]=='I'){
int lroot,rroot,newroot;
split(nowpos,root,lroot,rroot);
scanf("%d",&n);
int cnt=1;
char c=getchar();
while(cnt<=n){
c=getchar();
if(c>=32&&c<=126){
a[cnt]=c;
cnt++;
}
}
newroot=build(1,n);
root=merge(merge(lroot,newroot),rroot);
}
else if(opt[0]=='D'){
int lroot,tmproot,midroot,rroot;
scanf("%d",&n);
split(nowpos,root,lroot,tmproot);
split(n,tmproot,midroot,rroot);
root=merge(lroot,rroot);
}
else if(opt[0]=='G'){
int lroot,tmproot,midroot,rroot;
scanf("%d",&n);
split(nowpos,root,lroot,tmproot);
split(n,tmproot,midroot,rroot);
query(midroot);
printf("\n");
root=merge(lroot,merge(midroot,rroot));
}
else if(opt[0]=='P'){
nowpos--;
}
else if(opt[0]=='N'){
nowpos++;
}
}
return 0;
}