块状链表

参考：Tak_vin 的 博客 及相关代码。

这篇可能写的巨草，主要是给我自己看的。

一种根号数据结构，支持一个区间的动态插入和随时访问。

以 Luogu4008 [NOI2003] 文本编辑器 为例。

题意：

• 维护一个文本编辑器，支持：
• Move/Prev/Next 移动光标位置
• Insert 在光标处插入若干个字符
• Delete 删除光标后的若干个字符
• Get 输出光标后的若干个字符

块状链表的基本思想就是用链表将一个一个块串起来，对于一个操作，我们通常先找到目标位置所处的块及对应的位置，然后如果要插入/删除等，我们将把这个块分裂（即拆成两个块，再进行后续操作）。

基本操作

const int N=2*1024*1024+10;
const int M=1500;
char str[N];
char data[M+5][M+5];
int freelist[M+5],siz[M+5],nxt[M+5],freepos;
inline void Clear(){
    for(int i=1;i<=M-1;i++) freelist[i]=i;
    freepos=1;nxt[0]=-1;siz[0]=0;
}
inline int New(){return freelist[freepos++];}
inline void Del(int t){freelist[--freepos]=t;return;}
inline void Find(int &p,int &b){for(b=0;b!=-1&&p>siz[b];b=nxt[b]) p-=siz[b];}
inline void Fill(int b,int n,char *str,int e){
    if(b==-1) return;
    nxt[b]=e;siz[b]=n;
    memcpy(data[b],str,n);
}
inline void Split(int b,int p){
    if(b==-1||p==siz[b]) return;
    int t=New();
    Fill(t,siz[b]-p,data[b]+p,nxt[b]);
    nxt[b]=t;siz[b]=p;
}
inline void Maintain(int b){
    for(;b!=-1;b=nxt[b]){
        for(int t=nxt[b];t!=-1&&siz[b]+siz[t]<=M;t=nxt[b]){
            memcpy(data[b]+siz[b],data[t],siz[t]);
            siz[b]+=siz[t];nxt[b]=nxt[t];Del(t);
        }
    }
}

这些是块状链表的基本操作，从上至下每个函数分别是：初始化、新建块、删除块、寻找块的位置、填充块、分裂块、维持操作。有几点需要注意的：

• 对于新建块，为了防止内存过大，我们需要使用内存池。
• 寻找位置时，可以直接将 $b$ 和 $p$ 分别更新为找到的块以及所找的位置属于该块中的第几个位置，方便后续操作。
• 维持操作是合并较小块，以保证所有快的大小不过小。

具体操作

inline void Insert(int p,int n,char *str){
    int b,t,i;Find(p,b);Split(b,p);
    for(i=0;i+M<=n;i+=M){
        t=New();
        Fill(t,M,str+i,nxt[b]);
        nxt[b]=t;b=t;
    }
    if(n-i){
        t=New();Fill(t,n-i,str+i,nxt[b]);
        nxt[b]=t;
    }
    Maintain(b);
}
inline void Erase(int p,int n){
    int b,e;Find(p,b);Split(b,p);
    for(e=nxt[b];e!=-1&&n>siz[e];e=nxt[e]) n-=siz[e];
    Split(e,n);e=nxt[e];
    for(int t=nxt[b];t!=e;t=nxt[b]){nxt[b]=nxt[t];Del(t);}
    Maintain(b);
}
inline void Get(int p,int n,char *str){
    int b,t,i;Find(p,b);i=min(n,siz[b]-p);
    memcpy(str,data[b]+p,i);
    for(t=nxt[b];t!=-1&&i+siz[t]<=n;i+=siz[t],t=nxt[t]) memcpy(str+i,data[t],siz[t]);
    if(t!=-1&&n-i) memcpy(str+i,data[t],n-i);str[n]='\0';
}

从上到下每个函数分别为：插入，删除，获取字符。

• 插入字符时只需要分裂后以一个块长为单位创建新块直至插入完即可。
• 删除字符时只需要分裂后逐块删除即可，注意更新的全部是最左块（不删除的哪个）的 nxt。
• 获取字符类似，只是没有分裂的必要。
• 注意插入和删除字符后都需要 maintain 一下维护块的大小。

完整代码（Luogu4008 [NOI2003] 文本编辑器）

#include<bits/stdc++.h>
using namespace std;
const int N=2*1024*1024+10;
const int M=1500;
char str[N];
struct BlockList{
    char data[M+5][M+5];
    int freelist[M+5],siz[M+5],nxt[M+5],freepos;
    inline void Clear(){
        for(int i=1;i<=M-1;i++) freelist[i]=i;
        freepos=1;nxt[0]=-1;siz[0]=0;
    }
    inline int New(){return freelist[freepos++];}
    inline void Del(int t){freelist[--freepos]=t;return;}
    inline void Find(int &p,int &b){for(b=0;b!=-1&&p>siz[b];b=nxt[b]) p-=siz[b];}
    inline void Fill(int b,int n,char *str,int e){
        if(b==-1) return;
        nxt[b]=e;siz[b]=n;
        memcpy(data[b],str,n);
    }
    inline void Split(int b,int p){
        if(b==-1||p==siz[b]) return;
        int t=New();
        Fill(t,siz[b]-p,data[b]+p,nxt[b]);
        nxt[b]=t;siz[b]=p;
    }
    inline void Maintain(int b){
        for(;b!=-1;b=nxt[b]){
            for(int t=nxt[b];t!=-1&&siz[b]+siz[t]<=M;t=nxt[b]){
                memcpy(data[b]+siz[b],data[t],siz[t]);
                siz[b]+=siz[t];nxt[b]=nxt[t];Del(t);
            }
        }
    }
    inline void Insert(int p,int n,char *str){
        int b,t,i;Find(p,b);Split(b,p);
        for(i=0;i+M<=n;i+=M){
            t=New();
            Fill(t,M,str+i,nxt[b]);
            nxt[b]=t;b=t;
        }
        if(n-i){
            t=New();Fill(t,n-i,str+i,nxt[b]);
            nxt[b]=t;
        }
        Maintain(b);
    }
    inline void Erase(int p,int n){
        int b,e;Find(p,b);Split(b,p);
        for(e=nxt[b];e!=-1&&n>siz[e];e=nxt[e]) n-=siz[e];
        Split(e,n);e=nxt[e];
        for(int t=nxt[b];t!=e;t=nxt[b]){nxt[b]=nxt[t];Del(t);}
        Maintain(b);
    }
    inline void Get(int p,int n,char *str){
        int b,t,i;Find(p,b);i=min(n,siz[b]-p);
        memcpy(str,data[b]+p,i);
        for(t=nxt[b];t!=-1&&i+siz[t]<=n;i+=siz[t],t=nxt[t]) memcpy(str+i,data[t],siz[t]);
        if(t!=-1&&n-i) memcpy(str+i,data[t],n-i);str[n]='\0';
    }
}BL;
char opt[10];
int T,pos,n;
int main(){
    scanf("%d",&T);BL.Clear();
    while(T--){
        scanf("%s",opt);
        if(opt[0]=='M') scanf("%d",&pos);
        else if(opt[0]=='I'){
            scanf("%d",&n);
            for(int i=0;i<n;i++){
                str[i]=getchar();
                if(str[i]<32||str[i]>126) i--;
            }
            BL.Insert(pos,n,str);
        }
        else if(opt[0]=='D'){
            scanf("%d",&n);
            BL.Erase(pos,n);
        }
        else if(opt[0]=='G'){
            scanf("%d",&n);
            BL.Get(pos,n,str);
            puts(str);
        }
        else if(opt[0]=='P') pos--;
        else pos++;
    }
}