LINK：文本编辑器
这个东西感觉块状链表写细节挺多 (块状链表本来就难写
解释一下块状链表的做法：其实是一个个数组块 然后利用链表给链接起来 每个块的大小为sqrt(n).
这样插入删除的时候直接暴力插入删除即可 复杂度都是根号的。
插入的时候当前的块过大的时候就要分裂 查询时对于大小为0的块记得及时删除即可。(我没写过在口胡
看起来很直观。
但其实这道题 splay来写就好写的多。
插入的话先直接build成一个比较平衡的二叉树 然后直接把对应位置旋到根 把下一个位置旋到根的右儿子 这样插入的时候插到右儿子的左儿子上即可。
删除 查询同理。
前驱和后继 这个直接在splay上暴力寻找就行 反正期望复杂度logn.
Move操作的话需要记录一下某个点的子树大小在splay上跑就行了。
细节也不多 算是比较好写。
//#include<bits\stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define INF 5000000000000000000ll
#define ldb long double
#define pb push_back
#define get(x) x=read()
#define gt(x) scanf("%d",&x)
#define put(x) printf("%d\n",x)
#define putl(x) printf("%lld\n",x)
#define gc(a) scanf("%s",a+1)
#define rep(p,n,i) for(RE int i=p;i<=n;++i)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define fep(n,p,i) for(RE int i=n;i>=p;--i)
#define pii pair<int,int>
#define mk make_pair
#define RE register
#define P 1000000007
#define mod 1000000007
#define S second
#define F first
#define gf(x) scanf("%lf",&x)
#define ull unsigned long long
#define ui unsigned
#define pf push_front
#define pb push_back
#define popf pop_front
#define l(p) c[p][0]
#define r(p) c[p][1]
using namespace std;
const int MAXN=2000010;
int rt,n,id,top;
int c[MAXN][2],f[MAXN],sz[MAXN],q[MAXN];
char a[10],w[MAXN];
inline void pushup(int p)
{
sz[p]=sz[l(p)]+sz[r(p)]+1;
return;
}
inline int build(int l,int r)
{
if(l>r)return 0;
int mid=(l+r)>>1;
c[q[mid]][0]=build(l,mid-1);
c[q[mid]][1]=build(mid+1,r);
if(c[q[mid]][0])f[c[q[mid]][0]]=q[mid];
if(c[q[mid]][1])f[c[q[mid]][1]]=q[mid];
pushup(q[mid]);return q[mid];
}
inline int get_nex(int x)
{
x=c[x][1];
while(c[x][0])x=c[x][0];
return x;
}
inline void rotate(int x)
{
int old=f[x],oldf=f[old],k=c[old][1]==x;
c[old][k]=c[x][k^1];c[x][k^1]=old;
if(oldf)c[oldf][c[oldf][1]==old]=x;
if(c[old][k])f[c[old][k]]=old;
f[old]=x;f[x]=oldf;pushup(old);
}
inline void splay(int x,int y)
{
while(f[x]!=y)
{
int old=f[x];
if(f[old]!=y)rotate(((c[f[old]][1]==old)^(c[old][1]==x))?x:old);
rotate(x);
}
pushup(x);if(!y)rt=x;
}
inline int find(int x)
{
int ww=rt;
while(1)
{
if(sz[l(ww)]+1==x)return ww;
if(sz[l(ww)]>=x)ww=l(ww);
else x=x-sz[l(ww)]-1,ww=r(ww);
}
return -1;
}
inline void get_data(int x)
{
if(!x)return;
get_data(c[x][0]);
q[++top]=x;
get_data(c[x][1]);
}
inline int get_pre(int x)
{
x=c[x][0];
while(c[x][1])x=c[x][1];
return x;
}
int main()
{
//freopen("1.in","r",stdin);
gt(n);rt=++id;sz[id]=2;++id;c[1][1]=id;sz[id]=1;f[id]=1;
rep(1,n,i)
{
gc(a);
if(a[1]=='I')
{
int x;gt(x);top=0;
char ch=getchar();
while(x)
{
ch=getchar();
while((int)ch<32||(int)ch>126)ch=getchar();
w[++id]=ch;q[++top]=id;--x;
}
int ww=build(1,top);
int w1=get_nex(rt);splay(w1,rt);
c[w1][0]=ww;f[ww]=w1;pushup(w1);pushup(rt);
}
if(a[1]=='M')
{
int x;gt(x);++x;
int w=find(x);
splay(w,0);
}
if(a[1]=='D')
{
int x;gt(x);
x=sz[l(rt)]+1+x+1;
int ww=find(x);
splay(ww,rt);
c[ww][0]=0;
pushup(ww);pushup(rt);
}
if(a[1]=='G')
{
int x;gt(x);
x=sz[l(rt)]+1+x+1;
int ww=find(x);
splay(ww,rt);
top=0;get_data(c[ww][0]);
rep(1,top,i)printf("%c",w[q[i]]);
puts("");
}
if(a[1]=='P')splay(get_pre(rt),0);
if(a[1]=='N')splay(get_nex(rt),0);
}
return 0;
}