题解 P5599 【【XR-4】文本编辑器】

· · 题解

题目传送门。

题意简述：给定长度为 n 的文本串 a 和有 m 个单词的字典 s_i。q 次操作，每次求出字典内所有单词在 a[l,r] 的出现次数，或将 a[l,r] 替换为 t 不断重复的结果。

假设没有修改操作，且 m=1，即字典中只有一个单词，记该单词长度为 L。 一个自然的想法是可以求出对于每个位置 i，a[i-L+1,i] 是否匹配 s_1，记为 f_i\ (f_1,f_2,\cdots,f_{L-1}=0)，暴力匹配即可。

查询时，因为 [l,l],[l,l+1],\cdots,[l,l+L-2] 长度不够，显然无法匹配 s_1，又因为 [x-L+1,x]\ (x\geq l+L-1) 匹配时不受小于 l 的位置的影响，即不会因为 a[1,l-1] 消失而导致 [x-L+1,x] 的匹配情况改变（由于 x\geq l+L-1，所以 x-L+1\geq l）。因此直接查询 \sum_{j=x}^rf_j 即可。直接前缀和维护可以做到 \mathcal{O}(q+nL)，使用 KMP 可以优化到 \mathcal{O}(q+n)。

Subtask #3：如果有修改操作呢？事情就变得无比麻烦了。昨天尝试写了一下，甚至比正解还难写（doge）。

首先得处理这个循环的 t。当然，我不知道怎么处理，所以看了眼 s_r_f 的题解。 注意到题目中说 “与文件相比，单词的长度是非常小的（L\leq 50）”，那么就好好利用一下这个性质。

首先，f_{[l,l+L-2]} 肯定是没有什么好方法，只能暴力硬做，那么，这一部分的想法是：从 l-L+1 开始跑 KMP，匹配到 l+L-2 并暴力更新 f_{[l,l+L-2]} 即可。为什么要从 l-L+1 而不是 l 开始跑：f_l 是与 a_{l-L+1} 有关的，所以从 l 开始跑会导致 f_{[l,l+L-2]} 全为 0，这显然是错误的。

同样的，对于 f_{[r+1,r+L-1]}，从 r-L+2 开始跑 KMP，一直匹配到 r+L-1 并暴力更新 f_{[r+1,r+L-1]} 即可。

接下来处理中间那一大坨循环的 t，记其长度为 T。有一个并不显然但很好理解，同时也是最关键的性质：修改过后，f_i=f_{i+T}\ (l+L-1\leq i\leq r-T+1)，也就是这部分 f 会产生长度为 T 的循环节。根据题目所给条件，有 a_{[i,i-L+1]}=a_{[i+T,(i+T)-L+1]}（i 的范围同上），所以显然。因此，求出循环节并用线段树维护即可。

当然，说起来简单，还有很多需要注意的地方：

还有一些注意点（踩过的坑）：

这样，时间复杂度为 \mathcal(q(\log n+L)+\sum T)。

看到这里，你可能以为我已经讲完了。实际上并没有，这只是 m=1 的部分分。不过别担心，只要你会 AC 自动机，那么 m 为多少都不是问题。

注意到字典是固定的，所以我们对其建立 AC 自动机。那么只需要将 f_i 的定义改为：将 a[1,i] 放在 AC 自动机上跑到的位置 p 在 fail 树上与根节点之间的路径所包含的终止节点个数 val_p。即 val_p=\sum_{i=1}^m [endpos_i\in \mathrm{path}(p,root)]。一个套路的方法是将所有终止节点在 fail 树上的子树的 val 值 +1，这样可以 \mathcal{O}(1) 求 f_i。如果不理解上述方法，P5357，请。

注意到 f_i 定义中的 a[1,i] 可以改成 a[i-L+1,i]\ (L=\max|s_j|)，因为任何一个单词 s_j 与 a 在位置 i 的匹配情况不会受到 a_x\ (x\leq i-L) 的影响（最长的单词与 a 在位置 i 的匹配的第一个位置为 i-L+1）。

剩下来就和 m=1 几乎一模一样，只不过在暴力匹配时的方式从跑 KMP 变成了跑 AC 自动机。总时间复杂度 \mathcal{O}(\sum|s_i|+\sum|t_i|+q(\log n+L))，其中 L=\max |s_i|。

/*
    Powered by C++11.
    Author : Alex_Wei.
*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N=1e6+5;
const int L=50+5;
const int Q=1e5+5;
const int S=2e5+5;

// basic variables
int lc,nw,q;
ll mp[1<<7],f[N];
string ct;

struct ACAM{
    int cnt,son[S][62],fa[S],val[S];
    void ins(string s){
        int p=0;
        for(char it:s){
            if(!son[p][mp[it]])son[p][mp[it]]=++cnt;
            p=son[p][mp[it]];
        } val[p]++;
    } void build(){
        queue <int> q;
        for(int i=0;i<62;i++)if(son[0][i])q.push(son[0][i]);
        while(!q.empty()){
            int t=q.front(); q.pop();
            for(int i=0;i<62;i++)
                if(son[t][i])fa[son[t][i]]=son[fa[t]][i],q.push(son[t][i]);
                else son[t][i]=son[fa[t]][i];
            val[t]+=val[fa[t]];
        }
    } void run(){ // get f
        int p=0;
        for(int i=1;i<=lc;i++)f[i]=val[p=son[p][mp[ct[i-1]]]];
    }
}ac;

// query variables
ll id,len[Q],sum[Q];
vector <ll> pre[Q];
string qt[Q];

// lazytag & Segment Tree
string tmp;
struct lazy{
    int id,hd;
}; struct SegTree{
    ll val[N<<2],lpos;
    lazy laz[N<<2];
    void build(int l,int r,int x){
        if(l==r){
            val[x]=f[l];
            return;
        } int m=l+r>>1;
        build(l,m,x<<1),build(m+1,r,x<<1|1);
        val[x]=val[x<<1]+val[x<<1|1];
    } void mark(int l,int r,int x,int id,int hd){ // mark lazytag & update
        laz[x]={id,hd};
        int ori=l-hd,tl=(r-ori)%len[id],rid=(r-ori)/len[id];
        if(rid==0)val[x]=pre[id][tl]-(hd?pre[id][hd-1]:0);
        else val[x]=pre[id][tl]+(rid*sum[id]-(hd?pre[id][hd-1]:0));
    } void push(int l,int r,int x){ // pushdown
        if(laz[x].id){
            int m=l+r>>1;
            int id=laz[x].id,hd=laz[x].hd;
            int mid=(hd+(m-l+1))%len[id];
            mark(l,m,x<<1,id,hd);
            mark(m+1,r,x<<1|1,id,mid);
            laz[x].id=0;
        }
    } void modifyt(int l,int r,int ql,int qr,int x){ // tag
        if(ql<=l&&r<=qr){
            mark(l,r,x,id,(l-lpos)%len[id]);
            return;
        } int m=l+r>>1; push(l,r,x);
        if(ql<=m)modifyt(l,m,ql,qr,x<<1);
        if(m<qr)modifyt(m+1,r,ql,qr,x<<1|1);
        val[x]=val[x<<1]+val[x<<1|1]; 
    } void modifyc(int l,int r,int ql,int qr,int x,bool tg){ // brute force : change
        if(ql>qr)return;
        if(l==r){
            val[x]=f[l];
            if(tg)laz[x]={id,(l-lpos)%len[id]};
            return;
        } int m=l+r>>1; push(l,r,x);
        if(ql<=m)modifyc(l,m,ql,qr,x<<1,tg);
        if(m<qr)modifyc(m+1,r,ql,qr,x<<1|1,tg);
        val[x]=val[x<<1]+val[x<<1|1];
    } ll query(int l,int r,int ql,int qr,int x){
        if(ql>qr)return 0;
        if(ql<=l&&r<=qr)return val[x];
        ll m=l+r>>1,ans=0; push(l,r,x);
        if(ql<=m)ans+=query(l,m,ql,qr,x<<1);
        if(m<qr)ans+=query(m+1,r,ql,qr,x<<1|1);
        return ans;
    } void forms(int l,int r,int ql,int qr,int x){ // form current string [ql,qr]
        if(ql>qr)return;
        if(l==r){
            if(laz[x].id)tmp+=qt[laz[x].id][laz[x].hd];
            else tmp+=ct[l-1];
            return;
        } int m=l+r>>1; push(l,r,x);
        if(ql<=m)forms(l,m,ql,qr,x<<1);
        if(m<qr)forms(m+1,r,ql,qr,x<<1|1);
    }
}st;

int main(){
//  freopen("P5599_5.in","r",stdin);
//  freopen("P5599_5.out","w",stdout);
    // mp
    for(int i='A';i<='Z';i++)mp[i]=i-'A';
    for(int i='a';i<='z';i++)mp[i]=26+(i-'a');
    for(int i='0';i<='9';i++)mp[i]=52+(i-'0');

    // read & init
    cin>>lc>>nw>>q>>ct;
    for(int i=1;i<=nw;i++){
        string wrd;
        cin>>wrd,ac.ins(wrd);
    } ac.build(),ac.run(),st.build(1,lc,1);

    // solve
    for(int i=1;i<=q;i++){
        int op,l,r,ls; scanf("%d%d%d",&op,&l,&r),ls=r-l+1,st.lpos=l;
        if(op==1){
            ll rpos=min(r,l+L),ans=0,p=0;
            tmp="",st.forms(1,lc,l,rpos,1);
            for(int i=l;i<=rpos;i++)ans+=ac.val[p=ac.son[p][mp[tmp[i-l]]]];
            printf("%lld\n",ans+st.query(1,lc,rpos+1,r,1));
        } else{
            string t; cin>>t,len[++id]=t.size(),pre[id].resize(len[id]);
            int lpos=max(1,l-L+1),rpos=min(lc,r+L-1),p=0;
            if(ls<=L*2+len[id]*2){
                tmp="",st.forms(1,lc,lpos,rpos,1); // get current string
                for(int i=lpos;i<=rpos;i++){
                    char it=(i<l||i>r?tmp[i-lpos]:t[(i-l)%len[id]]);
                    p=ac.son[p][mp[it]];
                    if(i>=l)f[i]=ac.val[p];
                } st.modifyc(1,lc,l,r,1,1),st.modifyc(1,lc,r+1,rpos,1,0);
            } else{
                // front section : [l-L+1,l+L-1]
                int led=l+L-1,rbg=r-L+1;
                while((led-l)%len[id])led++;
                tmp="",st.forms(1,lc,lpos,l-1,1);
                for(int i=lpos;i<led+len[id];i++){
                    char it=(i<l?tmp[i-lpos]:t[(i-l)%len[id]]);
                    p=ac.son[p][mp[it]];
                    if(i>=l){
                        if(i<led)f[i]=ac.val[p];
                        else pre[id][i-led]=(i>led?pre[id][i-led-1]:0)+ac.val[p];
                    }
                } sum[id]=pre[id][len[id]-1];
                st.modifyc(1,lc,l,led-1,1,1),st.modifyt(1,lc,led,r,1);

                // back section
                tmp="",st.forms(1,lc,r+1,rpos,1),p=0;
                for(int i=rbg;i<=rpos;i++){
                    char it=(i>r?tmp[i-r-1]:t[(i-l)%len[id]]);
                    p=ac.son[p][mp[it]];
                    if(i>r)f[i]=ac.val[p];
                } st.modifyc(1,lc,r+1,rpos,1,0);
            } qt[id]=t;
        }
    }

    return 0;
}

如果您看懂了这篇题解就点个赞吧 qwq。