CF587FDuffisMad（AC自动机+树状数组+分块）

考虑两一个暴力

1

因为询问\([a,b]\)可以拆成\([1,b]\)-\([1,a-1]\)所以把询问离线，然后就是求\([1,x]\)中被\(S_i\)包含的串的数量。考虑当\([1,x-1]->[1,x]\)时我们把\(S_x\)结束节点在fail树的子树加1。然后询问就是求\(S_i\)在AC自动机上跑时经过所有点的点权用树状数组维护。设\(\sum{len[S_i]}=L\)这样的复杂度就是\(O(mLlogL)\)无法通过此题。

2

依然离线。这次我们把\(S_i\)放在fail树上跑时经过的点在fail树上加1。然后每一个x的贡献就是x的子树和。这个我们在fail树上DP（合并size）再做一个前缀合就能做到\(O(n)\)预处理\(O(1)\)查询。复杂度\(O(nL)\)无法通过此题。
然后我们对询问分块。长度大于\(sqrt(L)\)的用方法二，其他的用方法一。这样方法二最多用\(\sqrt{n}\)次。复杂度\(O(\sqrt{n}L)\)。方法一因为么次询问的串长最多为\(\sqrt{L}\)，所以复杂度为\(O(m\sqrt{L}logL)\)最终复杂度就是这两个加起来。可以通过此题。

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=201000;
const int M=501000;
int cnt,head[N];
int n,m;
long long ans[M];
int dfn[N],R[N],L[N],tot,LEN;
long long tr[N];
long long size[N],sum[N];
string s[N];
struct ques{
    int x,k,id;
    ques(int xx=0,int kk=0,int idd=0){
        x=xx;k=kk;id=idd;
    }
};
vector vec1[N],vec2[N];
struct edge{
    int to,nxt;
}e[N];
void add_edge(int u,int v){
    cnt++;
    e[cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int lowbit(int x){
    return x&-x;
}
void add(int x,int w){
    for(int i=x;i<=tot;i+=lowbit(i))tr[i]+=w;
}
long long getsum(int x){
    long long tmp=0;
    for(int i=x;i;i-=lowbit(i))tmp+=tr[i];
    return tmp;
}
void dfs(int u){
    dfn[u]=++tot;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        dfs(v);
    }
    R[u]=tot;
}
void dfs1(int u){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        dfs1(v);
        size[u]+=size[v];
    }   
}
struct AC{
    int point[N],trans[N][27],tot,fail[N];
    void ins(string s,int len,int k){
        int now=0;
        for(int i=0;i q;
        for(int i=1;i<=26;i++)if(trans[0][i])q.push(trans[0][i]);
        while(!q.empty()){
            int now=q.front();
            q.pop();
            for(int i=1;i<=26;i++){
                if(trans[now][i])fail[trans[now][i]]=trans[fail[now]][i],q.push(trans[now][i]);
                else trans[now][i]=trans[fail[now]][i];
            }
        }
    }
}ac;
int read(){
    int sum=0,f=1;char ch=getchar();
    while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch=&＃39;-&＃39;)f=-1;ch=getchar();}
    while(ch>=&＃39;0&＃39;&&ch<=&＃39;9&＃39;){sum=sum*10+ch-&＃39;0&＃39;;ch=getchar();}
    return sum*f;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
        cin>>s[i];
        L[i]=s[i].size();
        LEN+=L[i];
        ac.ins(s[i],L[i],i);
    }
    int hhh=getchar();
    int block=sqrt(LEN);
    ac.get_fail();
    for(int i=1;i<=ac.tot;i++)add_edge(ac.fail[i],i);
    dfs(0);
    for(int i=1;i<=m;i++){
        int a=read(),b=read(),c=read();
        if(L[c]>block){
            vec1[c].push_back(ques(b,1,i)),vec1[c].push_back(ques(a-1,-1,i));
        }
        else vec2[a-1].push_back(ques(c,-1,i)),vec2[b].push_back(ques(c,1,i));
    }
    for(int i=1;i<=n;i++){
        int now=0;
        for(int j=0;j

CF587F Duff is Mad（AC自动机+树状数组+分块）