题意
splay维护即可
code:
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000010;
int T,tot,points,root;
int fa[maxn],size[maxn];
int ch[maxn][2];
char str[maxn],s[maxn];
queue<int>pool;
inline int read()
{
char c=getchar();int res=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
return res*f;
}
inline void up(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+1;}
inline bool get(int x){return ch[fa[x]][1]==x;}
inline void rotate(int x)
{
int y=fa[x],z=fa[y],k=get(x),w=ch[x][k^1];
if(z)ch[z][get(y)]=x;ch[x][k^1]=y;ch[y][k]=w;
if(w)fa[w]=y;fa[y]=x;fa[x]=z;
up(y),up(x);
}
inline void splay(int x,int goal=0)
{
while(fa[x]!=goal)
{
int y=fa[x];
if(fa[y]!=goal)rotate(get(x)==get(y)?y:x);
rotate(x);
}
if(!goal)root=x;
}
inline int find(int x)
{
int now=root;
while(23333)
{
if(ch[now][0]&&x<=size[ch[now][0]])now=ch[now][0];
else if(x>size[ch[now][0]]+1)x-=size[ch[now][0]]+1,now=ch[now][1];
else return now;
}
}
inline int build(int l,int r,char* s)
{
if(l>r)return 0;
int now,mid=(l+r)>>1;
if(!pool.empty())now=pool.front(),pool.pop();
else now=++tot;
str[now]=s[mid];size[now]=1;
ch[now][0]=build(l,mid-1,s),ch[now][1]=build(mid+1,r,s);
if(ch[now][0])fa[ch[now][0]]=now;if(ch[now][1])fa[ch[now][1]]=now;
up(now);
return now;
}
inline void print(int x)
{
if(ch[x][0])print(ch[x][0]);
putchar(str[x]);
if(ch[x][1])print(ch[x][1]);
}
inline void recycle(int x)
{
if(ch[x][0])recycle(ch[x][0]);
if(ch[x][1])recycle(ch[x][1]);
pool.push(x);
fa[x]=ch[x][0]=ch[x][1]=0;
}
inline void insert()
{
int len=read();s[0]=' ';
for(int i=1;i<=len;i++)
{
s[i]=getchar();
if(s[i]=='
'||s[i]=='
')i--;
}
int x=find(points+1),y=find(points+2);
splay(x),splay(y,x);
int now=build(1,len,s);
ch[y][0]=now;fa[now]=y;
up(y),up(x);
}
inline void del()
{
int len=read();
int x=find(points+1),y=find(points+len+2);
splay(x),splay(y,x);
int now=ch[y][0];
recycle(now);ch[y][0]=0;
up(y),up(x);
}
inline void Get()
{
int len=read();
int x=find(points+1),y=find(points+len+2);
splay(x),splay(y,x);
print(ch[y][0]);
puts("");
}
inline void init()
{
root=++tot;str[root]='
',size[root]=1;
int tmp=++tot;fa[tmp]=root;str[tmp]='
',size[tmp]=1;ch[root][1]=tmp;
up(root);
}
int main()
{
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
T=read();
init();
while(T--)
{
char op[10];scanf("%s",op);
if(op[0]=='M')points=read();
if(op[0]=='I')insert();
if(op[0]=='D')del();
if(op[0]=='G')Get();
if(op[0]=='P')points--;
if(op[0]=='N')points++;
}
return 0;
}