题解：P4567 [AHOI2006] 文本编辑器

题解区好像暂时没有块状链表的题解。

从弱化版 P4008 过来的，建议先做弱化版，这篇题解是在弱化版的基础上讲的。 （相同操作的部分还是那边的题解更清晰）。

思路

对文本分块，这里块长取了 2000 左右，每块存储：

• 当前块中的字符串（我用的是 char 数组存）。
• 块的大小，即字符串长度（sz）。
• 翻转标记，类似于一些数据结构的懒标记（tag==1 表示需要翻转一次）。
  • 是否处于翻转的状态对整块插入、整块删除没有影响。
  • 整块翻转时只需要在块上打标记即可。
  • 涉及到对具体某一块修改时，需要先下放标记再修改。这一部分基本上是在分裂和合并的函数中实现的。
• 前驱块和后继块（pre 和 nxt），弱化版只需要记录后继就可以了。

具体操作

接下来是题目要求的操作（括号内的英文对应代码）：

光标移动

涉及到 Move Prev Next 操作，只需要直接对全局变量 pos（光标位置）赋值就可以了。

查询（fd）

这一部分和弱化版是一样的。

对于光标位置，返回一个 pair<int,int>，两个元素分别表示块的编号、块内位置。

分裂（split）与合并（merge）

不论是分裂还是合并，在分裂或合并前都需要将块转正（结构体中的 rev 函数）：如果 tag==1，则翻转整块的字符串并清空懒标记。如果是合并，需要将前后两块都转正 （好像是废话）。

然后分裂就是在后面新加一个块，维护好它的信息，合并就是删除一个块。这部分和弱化版是一样的。

插入（Insert）和删除（Delete）

这一部分和弱化版是一样的，因为我们已经把下方标记的部分放到 split 函数和 merge 函数里去了。

翻转（Rotate）

这部分是全新的操作。总体是和删除函数相似的，不同的地方在于，我们不是直接删掉那些定位到的块，而是 在块上打好翻转的标记并（用一个数组）依次记录下它们的编号，再倒序遍历数组，把它们插回去。即，块与块之间的顺序倒过来，并将每一块翻转。

查询（Get）

这里只需要查询光标后的一个字符就可以了。定位到光标位置的后一个字符（而不是光标） 之后，我们免去 split 操作，并调用一次 a[id].rev() 将这一块转成正的，输出对应字符就可以了。

一些细节

• 这题的读入和输出好像有点坑，关于换行符和题目中不存在的操作。
• 注意及时 merge 以保证时间复杂度。
• 如果链表的最后是 -1 结束，注意边界，避免调用 a_{-1}。
• 分裂合并的过程中随时更新 sz 的大小和对应块的字符串，在具体的块上单点操作时记得先下放标记。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define For(i,il,ir) for(int i=(il);i<=(ir);++i)
#define Fr(i,il,ir) for(int i=(il);i<(ir);++i)
#define Forr(i,ir,il) for(int i=(ir);i>=(il);--i)
using namespace std;
typedef pair<int,int> pii;
template<typename T>
inline void rd(T& x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') f=1; ch=getchar(); }
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename T,typename... Args>
void rd(T& first,Args&... args){ rd(first),rd(args...); }
const int B=2010;

struct node{
    bool tag;
    char ch[B<<1];
    int pre,nxt,sz;
    void rev(){ if(tag) reverse(ch+1,ch+1+sz),tag^=1; }
    void mdf(int x,int y,int z){ pre=x,nxt=y,sz=z; }
    void add(char c){ ch[++sz]=c; }
}a[B<<2];

int delv[B<<2];
int mxuse,deltot;
int newnode(){
    int id=deltot?delv[deltot--]:++mxuse;
    a[id].tag=0;return id;
}
void del(int x){ a[x].tag=0;delv[++deltot]=x; }

pii fd(int p){
    int sum=0;
    if(p==0) return mk(1,0);
    for(int u=1;~u;sum+=a[u].sz,u=a[u].nxt)
        if(sum<p&&p<=sum+a[u].sz)
            return mk(u,p-sum);
}
void split(pii x){
    a[x.fi].rev();
    int y=newnode();
    a[y].mdf(x.fi,a[x.fi].nxt,a[x.fi].sz-x.se);
    memcpy(a[y].ch+1,a[x.fi].ch+x.se+1,a[y].sz);
    a[x.fi].nxt=y,a[x.fi].sz=x.se;
}
void merge(int id){
    int y=a[id].nxt;
    if(y==-1||a[id].sz+a[y].sz>B||a[y].sz==0) return;
    a[id].rev(),a[y].rev();
    memcpy(a[id].ch+a[id].sz+1,a[y].ch+1,a[y].sz);
    a[id].nxt=a[y].nxt,a[id].sz+=a[y].sz;
    del(y);
}
int insblock(int lst)
{
    int x=newnode();
    a[x].mdf(lst,a[lst].nxt,0);
    if(~a[lst].nxt) a[a[lst].nxt].pre=x;
    a[lst].nxt=x;
    return x;
}

int n;
int pos,len;
void Insert()
{
    pii t=fd(pos);
    if(t.se<a[t.fi].sz) split(t);
    int id=t.fi;
    For(i,1,len)
    {
        if(i%B==1) id=insblock(id);
        char c=getchar();while((c<32||c>126)&&c!='\n'&&c!='\r') c=getchar();
        a[id].add(c);
    }
    merge(id);merge(t.fi);
}
void Delete()
{
    pii t=fd(pos);
    if(t.se<a[t.fi].sz) split(t);
    int id=t.fi;
    while(len>0)
    {
        int y=a[id].nxt;
        if(a[y].sz>len) split({y,len});
        a[id].nxt=a[y].nxt,len-=a[y].sz,del(y);
    }
    merge(t.fi);
}
int tmp[B<<1],totid=0;
void Rotate()
{
    pii t=fd(pos);
    if(t.se<a[t.fi].sz) split(t);
    int head=t.fi,tail=a[head].nxt,id=t.fi;totid=0;
    while(len>0)
    {
        int y=a[id].nxt;
        if(a[y].sz>len) split({y,len});
        a[y].tag^=1,len-=a[y].sz,id=y;
        tmp[++totid]=y,tail=a[y].nxt;
    }
    Forr(i,totid,1){
        a[head].nxt=tmp[i];
        a[tmp[i]].pre=head;
        head=tmp[i];
    }
    a[head].nxt=tail;
    merge(head),merge(t.fi);
    if(~tail) a[tail].pre=head;
}
void Get()
{
    pii t=fd(pos);
    int id=t.fi,i=t.se;
    if(i==a[id].sz) id=a[id].nxt,i=0;
    a[id].rev();++i;
    putchar(a[id].ch[i]);
    if(a[id].ch[i]!='\n'&&a[id].ch[i]!='\r') putchar('\n');
}
signed main()
{
    rd(n);a[newnode()].nxt=-1;
    while(n--)
    {
        char op=getchar();
        while(op!='M'&&op!='I'&&op!='D'&&op!='G'&&op!='P'&&op!='N'&&op!='R'){
            op=getchar();
            if(op==EOF) return 0;
        }
        if(op=='M') rd(pos);
        else if(op=='I') rd(len),Insert();
        else if(op=='D') rd(len),Delete();
        else if(op=='R') rd(len),Rotate();
        else if(op=='G') Get();
        else if(op=='P'||op=='N') getchar(),getchar(),getchar(),pos+=(op=='P'?-1:1);
    }
    return 0;
}

宣传：数据生成器。