1. 题目

传送门=￣ω￣=

2. 题解

//一开始一遍写完一遍编译通过，然后觉得可能有问题就手写了一下题目描述中的样例，结果发现程序不出结果，调了 20 分钟。。。最后发现程序没问题，是自己样例写错了，直接用它的样例就能过了。然后居然 1A 惹～

基本上可以说是维修数列的简化版了。

维修数列参见：传送门=￣ω￣=

这题还不用下传标记，要记录的值也很少，就不做过多赘述了。

代码：

#include <bits/stdc++.h>
using namespace std;
struct N{int f,s[2],sz;char d;}e[2000000];
int t,P=1,cnt,root;
char opt[10],str[2000000];
bool pos(int a){return e[e[a].f].s[1]==a;}
void pup(int a){e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+1;}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    pup(f),pup(a);
}
void splay(int a,int t)
{
    for(;e[a].f!=t;rot(a))if(e[e[a].f].f!=t)
        if(pos(a)^pos(e[a].f))rot(a);
        else rot(e[a].f);
    if(!t)root=a;
}
int find_by_order(int k)
{
    int a=root;
    while(root)
    {
        if(k<=e[e[a].s[0]].sz)a=e[a].s[0];
        else
        {
            k-=e[e[a].s[0]].sz+1;
            if(!k)return a;
            a=e[a].s[1];
        }
    }
    return 0;
}
void get_seg(int&l,int&r)
{
    r+=l+1,l=find_by_order(l),r=find_by_order(r);
    splay(l,0),splay(r,l);
}
void getstring(int len)
{
    for(int i=0;i<len;i++)
        if((str[i]=getchar())=='\n'||str[i]=='\r'){i--;continue;}
    str[len]='\0';
}
int build(int l,int r,int fa)
{
    if(l>r)return 0;
    int mid=(l+r)>>1,a=++cnt;
    e[a].f=fa,e[a].d=str[mid];
    e[a].s[0]=build(l,mid-1,a),e[a].s[1]=build(mid+1,r,a),pup(a);
    return a;
}
void work_insert()
{
    int len,l=P,r=0;
    scanf("%d",&len),getstring(len),get_seg(l,r);
    e[r].s[0]=build(0,len-1,r),pup(r),pup(l);
}
void work_del()
{
    int l=P,r;
    scanf("%d",&r),get_seg(l,r),e[r].s[0]=0,pup(r),pup(l);
}
void dfs_get(int a)
{
    if(!a)return;
    dfs_get(e[a].s[0]),putchar(e[a].d),dfs_get(e[a].s[1]);
}
void work_get()
{
    int l=P,r;
    scanf("%d",&r),get_seg(l,r),dfs_get(e[r].s[0]),putchar('\n');
}
int main()
{
    scanf("%d",&t);
    root=1,cnt=2,e[1].s[1]=2,e[1].sz=2,e[2].f=1,e[2].sz=1;
    while(t--)
    {
        scanf("%s",opt);
        if(opt[0]=='M')scanf("%d",&P),P++;
        else if(opt[0]=='P')P--;
        else if(opt[0]=='N')P++;
        else if(opt[0]=='I')work_insert();
        else if(opt[0]=='D')work_del();
        else work_get();
    }
    return 0;
}