专栏文章

题解：P10176 「OICon-02」Native Faith

ZZaunese
P10176题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqdr0kx
此快照首次捕获于
2025/12/04 03:08
3 个月前
此快照最后确认于
2025/12/04 03:08
3 个月前
查看原文
有代码的题解。
主要说明 fjy666 的第一种做法。省选场上能写出第二种做法（代码 7KB 以上）的都是这个👍👍👍。
由 n,m,q≤105n,m,q\le10^5，时限 3s，数据范围里有 ∑∣si∣\sum|s_i|，鉴定为：根号分治。
那么，依据串长度和 BB 的大小关系，分为大串和小串。
考虑一个暴力。记询问为 (l,r,k)(l,r,k)，枚举 sks_k 被分割出的前缀长度 ii，此时的方案数是：sks_k 的长为 ii 的前缀在 sl,sl+1,…,srs_l,s_{l+1},\dots,s_r 中的出现次数和 fif_i，与 sks_k 的长为 ∣sk∣−i|s_k|-i 的后缀在 sl,sl+1,…,srs_l,s_{l+1},\dots,s_r 中的出现次数和 gig_i 的积，即此询问答案为
∑i=1∣sk∣−1figi\sum_{i=1}^{|s_k|-1}f_ig_i
求这个出现次数显然使用 AC 自动机。
但是这里，模板串是 sks_k 的所有前缀、后缀，故想到先对所有 sks_k 的所有前缀构建 AC 自动机，对所有 sks_k 的所有后缀再构建一个 AC 自动机。
然后扫描线，询问差分一下，拆成 (l−1,k)(l-1,k) 和 (r,k)(r,k)，变成前缀 s1,s2,…,sis_1,s_2,\dots,s_i 查询某模板串的出现次数和。
依次加入字符串，即在两个自动机上分别跑一遍，然后查询出现次数和显然是 Fail 树的某棵子树的点权和。即单点加子树求和。
此时发现枚举分割的复杂度已经有 O(∑∣sk∣)O\left(\sum|s_k|\right) 了，能解决 ∣sk∣≤B|s_k|\le B 的问题。子树求和有 O(qB)O(qB) 次，单点加有 O(m)O(m) 次（即在自动机上跑一遍），用 O(m)O\left(\sqrt m\right) 的单点加、O(1)O(1) 的区间求和的分块来平衡，时间复杂度 O(qB+mm)O\left(qB+m\sqrt m\right)。
然后解决 ∣sk∣>B|s_k|> B 的问题。
考虑小串对大串的贡献。注意到能产生贡献当且仅当分割出的前缀长度 i≤Bi\le B 或 i≥∣sk∣−Bi\ge|s_k|-B。枚举这一范围的 ii 也只要 O(B)O(B) 的时间复杂度，继续使用上面的暴力即可。
接下来只要关心 i>Bi> B 且 i<∣sk∣−Bi<|s_k|-B 的情况，显然只有大串能贡献。
由于大串只有 O(mB)O\left(\frac mB\right) 个，枚举分割后只需回答 O((mB)2)O\left(\left(\frac mB\right)^2\right) 个本质不同的问题，时间复杂度是 O(m3B2)O\left(\frac{m^3}{B^2}\right)。
具体地，沿用上述的扫描线，求每个大串 sis_i 的每个前缀、后缀在每个大串序列前缀 s1,s2,…,sjs_1,s_2,\dots,s_j 的出现次数和。这个部分的时间复杂度是 O(mm+m×mB)O\left(m\sqrt m+m\times\frac mB\right)。
回答询问的时候直接对 O((mB)3)O\left(\left(\frac mB\right)^3\right) 个本质不同的询问记忆化即可。
两部分复杂度分别是 O(qB)O(qB) 和 O(m3B2)O\left(\frac{m^3}{B^2}\right)，若 n,m,qn,m,q 同阶则平衡得到 B=n2/3B=n^{2/3}，总时间复杂度 O(n5/3)O(n^{5/3})。
空间复杂度是 O(qB+m2B+(mB)3)O\left(qB+\frac{m^2}B+\left(\frac mB\right)^3\right)。块长取到 500500，大一点会 MLE。
代码参考了 https://www.luogu.com.cn/record/187393706，在此表示感谢！
CPP
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<string>

#define fi first
#define se second
#define mkp std::make_pair
using llu=long long unsigned;
using ll=long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}

const int NV=1e5,B=500; //2100 -> 500

int M;

namespace bar{
    int bel[NV+5],L[NV+5],R[NV+5];
    void init(){
        for(int i=1;i<=M;++i){
            bel[i]=(i-1)/B+1;
            if(!L[bel[i]]) L[bel[i]]=i;
            R[bel[i]]=i;
        }
    }
}

struct ac{
    struct ACN{
        int g[26],f,p;
    } tr[NV+5];
    int cnt;
    void ins(const char*sz){
        int p=0;
        for(int i=0;sz[i];++i){
            const int c=sz[i]-'a';
            if(!tr[p].g[c]) tr[tr[p].g[c]=++cnt].p=p;
            p=tr[p].g[c];
        }
    }
    struct EDGE{
        int t,n;
    } G[NV+5];
    int ecnt=2,hd[NV+5],dfc,dfn[NV+5],dfr[NV+5];
    void ade(int s,int t){
        G[ecnt]={t,hd[s]};
        hd[s]=ecnt++;
    }
    void dfs(int x){
        dfn[x]=++dfc;
        for(int e=hd[x];e;e=G[e].n) dfs(G[e].t);
        dfr[x]=dfc;
    }void build(){
        std::queue<int> q;
        for(int i=0;i<26;++i) if(tr[0].g[i]) q.push(tr[0].g[i]);
        while(q.size()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;++i)
                if(tr[u].g[i]){
                    tr[tr[u].g[i]].f=tr[tr[u].f].g[i];
                    q.push(tr[u].g[i]);
                }else tr[u].g[i]=tr[tr[u].f].g[i];
        }
        for(int i=1;i<=cnt;++i) ade(tr[i].f,i);
        dfc=0;
        dfs(0);
    }
    int bis[NV+5],bgs[NV+5];
    void add(int p,int z){ // point add
        for(int i=p;i<=bar::R[bar::bel[p]];++i) bis[i]+=z;
        for(int i=bar::bel[p];i<=bar::bel[M];++i) bgs[i]+=z;
    }int que(int p){ // prefix sum
        return p?bis[p]+bgs[bar::bel[p]-1]:0;
    }int que(int l,int r){
        return que(r)-que(l-1);
    }void tour(const char*sz){
        int p=0;
        for(int i=0;sz[i];++i){
            p=tr[p].g[sz[i]-'a'];
            add(dfn[p],1);
        }
    }void clr(){
        memset(tr,0,sizeof*tr*(cnt+1));
        ecnt=2;
        memset(hd,0,sizeof*hd*(cnt+1));
        memset(bis,0,sizeof bis);
        memset(bgs,0,sizeof bgs);
        cnt=0;
    }auto que(const char*s,bool op=0){
        std::vector<int> ans;
		int mxn=!op?B-1:1<<30,p=0;
		for(int i=0;i<=mxn&&s[i];++i){
			p=tr[p].g[s[i]-'a'];
			ans.push_back(que(dfn[p],dfr[p]));
		}
        return ans;
	}
} pac,sac;

namespace xm{
    std::string s[NV+5],rs[NV+5];
    std::vector<int> swq[NV+5],pinfo[NV+5],sinfo[NV+5],npi[205][205],nsi[205][205];
    std::pair<int,int> quer[NV+5];
    ll mem[205][205][205];
    int quek[NV+5],bid[NV+5],bli[NV+5],nxt[205][205][205];
    char buf[NV+5];
    void _(){
        int N,Q;

        scanf("%d%d",&N,&Q);
        for(int i=1;i<=N;++i){
            scanf("%s",buf);
            rs[i]=s[i]=buf;
            std::reverse(rs[i].begin(),rs[i].end());
            M+=s[i].size();
        }
        bar::init();
        for(int i=1;i<=Q;++i){
            int l,r;
            scanf("%d%d%d",&l,&r,&quek[i]);
            quer[i]={l,r};
            swq[l-1].push_back(-i);
            swq[r].push_back(i);
        }

        for(int i=1;i<=N;++i){
            pac.ins(s[i].c_str());
            sac.ins(rs[i].c_str());
        }
        pac.build();
        sac.build();
        for(int i=0;i<=N;++i){
            if(i){
                pac.tour(s[i].c_str());
                sac.tour(rs[i].c_str());
            }
            for(int qi:swq[i]){
                const int sgn=qi>0?1:-1;
                qi=std::abs(qi);
                const int u=quek[qi];
                if(sgn<0){
                    pinfo[qi]=pac.que(s[u].c_str());
                    sinfo[qi]=sac.que(rs[u].c_str());
                }else{
                    auto ret=pac.que(s[u].c_str());
                    for(int i=0;i<ret.size();++i) pinfo[qi][i]=ret[i]-pinfo[qi][i];
                    ret=sac.que(rs[u].c_str());
                    for(int i=0;i<ret.size();++i) sinfo[qi][i]=ret[i]-sinfo[qi][i];
                }
            }
        }

        pac.clr();
        sac.clr();
        for(int i=1;i<=N;++i) if(s[i].size()>B){
            bli[bid[i]=++*bli]=i;
            pac.ins(s[i].c_str());
            sac.ins(rs[i].c_str());
        }
        pac.build();
        sac.build();
        for(int i=1;i<=*bli;++i){
            pac.tour(s[bli[i]].c_str());
            sac.tour(rs[bli[i]].c_str());
            for(int j=1;j<=*bli;++j){
                npi[i][j]=pac.que(s[bli[j]].c_str(),1);
                nsi[i][j]=sac.que(rs[bli[j]].c_str(),1);
            }
        }
        for(int j=1;j<=*bli;++j){
            npi[0][j].resize(M);
            nsi[0][j].resize(M);
        }

        for(int i=1;i<=Q;++i) if(s[quek[i]].size()>B){
            ll ans=0;
            int l=0,r=0,sle=s[quek[i]].size(),sid=bid[quek[i]];
			for(int j=1;j<=*bli;++j){
				if(bli[j]<quer[i].fi) l=j;
				if(bli[j]<=quer[i].se) r=j;
			}
            for(int j=0;j<sle-1;++j){
				if(j>=(int)pinfo[i].size()&&(int)sinfo[i].size()<=sle-j-2){
					if(mem[l][r][sid]){
						ans+=mem[l][r][sid];
						j=nxt[l][r][sid];
					}else{
						for(;j>=(int)pinfo[i].size()&&(int)sinfo[i].size()<=sle-j-2;++j){
							const int pv=npi[r][sid][j]-npi[l][sid][j];
							const int sv=nsi[r][sid][sle-j-2]-nsi[l][sid][sle-j-2];
							mem[l][r][sid]+=(ll)pv*sv;
						}
                        --j;
						nxt[l][r][sid]=j;
						ans+=mem[l][r][sid];
					}
					continue;
				}
                int pv,sv;
                if(j>=(int)pinfo[i].size()) pv=npi[r][sid][j]-npi[l][sid][j];
                else pv=pinfo[i][j];
                if((int)sinfo[i].size()<=sle-j-2)
                    sv=nsi[r][sid][sle-j-2]-nsi[l][sid][sle-j-2];
                else sv=sinfo[i][sle-j-2];
                ans+=(ll)pv*sv;
            }

            printf("%lld\n",ans);
        }else{
            int le=pinfo[i].size();
            ll ans=0;
            for(int j=0;j<le-1;++j)
                ans+=(ll)pinfo[i][j]*sinfo[i][le-j-2];
            printf("%lld\n",ans);
        }
    }
}

int main(){
    xm::_();
    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...