题解 P4008 【[NOI2003]editor文本编辑器】
两种做法都介绍一下。
块状链表
优点是代码写起来比写splay爽一些，而且更为直观（本蒟蒻的代码只有90分）
块状链表是一个个数组块，用链表穿起来得到的结果，解决了普通数组插入的困难和普通链表查询的困难，一种根号复杂度的数据结构。
插入的时候要记得当导致块过大的时候就要分裂，查询的时候要记得去除大小为0的块，以及每次移动光标的时候去移动记录光标在块状链表位置的两个指针会更快一些。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ksz 2000
int T,b1=1,b2,cn=1,gb,len;
struct node{char a[2300];int sz,pre,nxt;} p[7005];
void move() {//移动光标，即查询操作，暴力找块大小即可
int pos;scanf("%d",&pos);
b1=p[0].nxt;int tot=0;
while(tot+p[b1].sz<pos) tot+=p[b1].sz,b1=p[b1].nxt;
b2=pos-tot;
}
void ins() {//插入操作
char ch;int d1=b1,d2=b2;
while(len--) {
ch=getchar();while(ch<32||ch>126) ch=getchar();
if(p[d1].sz==ksz) {//注意不要让块变得太大了
++cn,p[cn].pre=d1,p[cn].nxt=p[d1].nxt;
p[p[d1].nxt].pre=cn,p[d1].nxt=cn;
for(int i=d2+1;i<=p[d1].sz;++i) p[cn].a[++p[cn].sz]=p[d1].a[i];
p[d1].sz=d2,d1=cn,d2=0;
}
for(int i=p[d1].sz;i>d2;--i) p[d1].a[i+1]=p[d1].a[i];
++p[d1].sz,p[d1].a[++d2]=ch;
}
}
void del() {//删除操作
int d1=b1,d2=b2;
while(len) {//切记不要一个一个的删，太慢了！
int kl=p[d1].sz-d2;
if(len>kl) len-=kl,p[d1].sz=d2,d1=p[d1].nxt,d2=0;
else {
for(int i=d2+len+1;i<=p[d1].sz;++i) p[d1].a[i-len]=p[d1].a[i];
p[d1].sz-=len,len=0;
}
}
}
//去除为0的块是非常非常重要的
void query() {//查询操作
int d1=b1,d2=b2;
while(len) {//也不要一个一个地输出
while(!p[d1].sz)
p[p[d1].pre].nxt=p[d1].nxt,p[p[d1].nxt].pre=p[d1].pre,d1=p[d1].nxt;
int kl=p[d1].sz-d2;
if(len>kl) {
for(int i=d2+1;i<=p[d1].sz;++i) putchar(p[d1].a[i]);
len-=kl,d1=p[d1].nxt,d2=0;
}
else {
for(int i=1;i<=len;++i) putchar(p[d1].a[i+d2]);
len=0;
}
}
puts("");
}
void move_front() {
if(b2) --b2;
else {
b1=p[b1].pre;
while(!p[b1].sz)
p[p[b1].pre].nxt=p[b1].nxt,p[p[b1].nxt].pre=p[b1].pre,b1=p[b1].nxt;
b2=p[b1].sz-1;//!!!
}
}
void move_next() {
if(b2<p[b1].sz) ++b2;
else {
b1=p[b1].nxt,b2=1;
while(!p[b1].sz)
p[p[b1].pre].nxt=p[b1].nxt,p[p[b1].nxt].pre=p[b1].pre,b1=p[b1].nxt;
}
}
int main()
{
char ch[10];
scanf("%d",&T),p[0].nxt=1;
while(T--) {
scanf("%s",ch);
if(ch[0]=='M') move();
else if(ch[0]=='I') scanf("%d",&len),ins();
else if(ch[0]=='D') scanf("%d",&len),del();
else if(ch[0]=='G') scanf("%d",&len),query();
else if(ch[0]=='P') move_front();
else move_next();
}
return 0;
}splay
优点是快，万能。缺点就是代码打得浑身难受。
身为序列之王的splay，不会被这种题目难倒。如果你是首次接触splay，卖个安利
那么此题涉及的splay操作就是查询第k个数，插入，删除，和输出。对于熟练splay的人应该不难，可以看代码的注释。
总之，如果要对一个区间进行操作，就把区间左端点的左边那个点splay到根，右端点右边那个点splay到根的右儿子，然后对根的右儿子的左子树进行操作。
#include<bits/stdc++.h>
using namespace std;
const int N=2100000;
int T,GB,len,rot,trs,sss;
int son[N][2],f[N],siz[N];char c[N],s[N];
void up(int x) {siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;}
int is(int x) {return son[f[x]][1]==x;}
void spin(int x,int &mb) {//旋转操作
int fa=f[x],g=f[fa],t=is(x);
if(fa==mb) mb=x;
else son[g][is(fa)]=x;
f[fa]=x,f[x]=g,f[son[x][t^1]]=fa;
son[fa][t]=son[x][t^1],son[x][t^1]=fa;
up(fa),up(x);
}
void splay(int x,int &mb) {//splay操作
while(x!=mb) {
if(f[x]!=mb) {
if(is(x)^is(f[x])) spin(x,mb);
else spin(f[x],mb);
}
spin(x,mb);
}
}
int find(int x,int kth) {//查找第k个数
if(siz[son[x][0]]+1==kth) return x;
if(siz[son[x][0]]>=kth) return find(son[x][0],kth);
return find(son[x][1],kth-siz[son[x][0]]-1);
}
void build(int l,int r,int fa,int fnum,char *s) {//建树
if(l>r) return;
int mid=(l+r)>>1,t;
++sss,t=sss;
if(l!=r) build(l,mid-1,t,0,s),build(mid+1,r,t,1,s);
c[t]=s[mid],f[t]=fa,son[fa][fnum]=t,up(t);
}
void print(int x) {//按照左根右的顺序进行输出
if(son[x][0]) print(son[x][0]);
putchar(c[x]);
if(son[x][1]) print(son[x][1]);
}
int main()
{
char ch[20];int x,y,l,r;
scanf("%d",&T);
ch[0]=ch[1]=ch[2]=c[0]=' ',rot=1,build(1,2,0,0,ch);
while(T--) {
scanf("%s",ch);
if(ch[0]=='M') scanf("%d",&GB);//GB:光标位置
else if(ch[0]=='I') {
scanf("%d",&len),trs+=len,s[0]=' ';
for(int i=1;i<=len;++i) {
s[i]=getchar();
if(s[i]=='\n'||s[i]=='\r') --i;
}
x=find(rot,GB+1),y=find(rot,GB+2);
splay(x,rot),splay(y,son[x][1]),build(1,len,y,0,s);//先建立一棵子树后再插入，保证平衡
}
else if(ch[0]=='D') {
scanf("%d",&len),len=min(len,trs-GB),trs-=len;
x=find(rot,GB+1),y=find(rot,GB+len+2);
splay(x,rot),splay(y,son[x][1]),son[y][0]=0;//删除区间，不用垃圾回收
}
else if(ch[0]=='G') {
scanf("%d",&len),len=min(len,trs-GB);
x=find(rot,GB+1),y=find(rot,GB+len+2);
splay(x,rot),splay(y,son[x][1]),print(son[y][0]),puts("");//输出
}
else if(ch[0]=='P') --GB;
else if(ch[0]=='N') ++GB;
}
return 0;
}