分析:

Splay区间操作裸题,维护出区间信息,按照要求模拟,注意读入格式,并且考虑内存回收(开不下)

附上代码:

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <map>
using namespace std;
#define N 2097200
#define ls ch[rt][0]
#define rs ch[rt][1]
#define get(rt) (ch[f[rt]][0]!=rt)
int ch[N][2],f[N],cnt,siz[N],val[N],S[N],top,rot,pos,size,rev[N];char op[20],s[N];
void clear(int rt)
{
rev[rt]=ch[rt][0]=ch[rt][1]=f[rt]=siz[rt]=val[rt]=0;
}
void PushUp(int rt)
{
if(rt)siz[rt]=siz[ls]+siz[rs]+1;
}
void PushDown(int rt)
{
if(rev[rt])
{
if(ls)rev[ls]^=1,swap(ch[ls][0],ch[ls][1]);
if(rs)rev[rs]^=1,swap(ch[rs][0],ch[rs][1]);
rev[rt]=0;
}
}
int new_node()
{
int rt;
if(top)rt=S[--top];
else rt=++cnt;
clear(rt);
return rt;
}
void rotate(int rt)
{
int x=f[rt],y=f[x],k=get(rt);
if(y)ch[y][ch[y][0]!=x]=rt;
ch[x][k]=ch[rt][!k];f[ch[x][k]]=x;
ch[rt][!k]=x;f[x]=rt;f[rt]=y;
if(rot==x)rot=rt;PushUp(x);PushUp(rt);
}
void Splay(int rt,int y)
{
for(int fa;(fa=f[rt])!=y;rotate(rt))
if(f[fa]!=y)
rotate((get(fa)==get(rt))?fa:rt);
}
void build(int fa,int l,int r,bool flg)
{
if(l>r)return ;
int m=(l+r)>>1,rt=new_node();
val[rt]=s[m];ch[fa][flg]=rt;f[rt]=fa;
build(rt,l,m-1,0);build(rt,m+1,r,1);PushUp(rt);
}
int find(int x)
{
int rt=rot;
while(1)
{
PushDown(rt);
if(siz[ls]>=x)rt=ls;
else
{
x-=siz[ls]+1;
if(!x)return rt;
rt=rs;
}
}
}
void rec(int rt)
{
if(!rt)return ;
if(ls)rec(ls);ls=0;if(rs)rec(rs);rs=0;
clear(rt);S[top++]=rt;
}
void insert(int len)
{
int x=find(pos),rt=find(pos+1);Splay(x,0);Splay(rt,rot);
build(rt,1,len,0);PushUp(rt);PushUp(x);
}
void del(int len)
{
int x=find(pos),rt=find(pos+len+1);Splay(x,0);Splay(rt,rot);
rec(ls);ls=0;PushUp(rt);PushUp(x);
}
void reverse(int len)
{
int x=find(pos),y=find(pos+len+1);Splay(x,0);Splay(y,rot);
int rt=ch[y][0];swap(ls,rs);rev[rt]^=1;
}
int main()
{
int Q;
scanf("%d",&Q);
siz[1]=2,siz[2]=1,ch[1][1]=2,f[2]=1,rot=pos=1,size=cnt=2;
while(Q--)
{
int x;
scanf("%s",op);
if(op[0]=='M')scanf("%d",&x),pos=x+1;
else if(op[0]=='I')
{
scanf("%d",&x);
for(int i=1;i<=x;i++)
{
s[i]=getchar();
while(s[i]>126||s[i]<32)s[i]=getchar();
}
s[x+1]='\0';
//printf("%s",s+1);
insert(x);size+=x;
}else if(op[0]=='D')
{
scanf("%d",&x);
if(x+pos+1>size)x=size-pos-1;
del(x);size-=x;
}else if(op[0]=='N')pos+=(pos!=size);
else if(op[0]=='P')pos-=(pos>0);
else if(op[0]=='G')
{
int y=find(pos),rt=find(pos+2);
Splay(y,0);Splay(rt,rot);
printf("%c\n",val[ls]);
}else
{
scanf("%d",&x);
if(x+pos+1>size)x=size-pos-1;
reverse(x);
}
}
return 0;
}

  

05-08 14:57