CF587F Duff is Mad

题目描述

题解：

有个$O(sum 询问k串长)$的做法就不说了。

当然是过不去的。

貌似第22个点总长1e5只有三个串

所以考虑对询问的$k$串串长分开算。

先建$fail$树。

对于$s_k>=sqrt{n}$的串，最多只有$sqrt{n}$个。可以枚举然后$dfs$一遍，求出每个结束位置$fail$树子树内有多少个$s_k$的前缀。

然后用前缀和维护，对于每组询问$O(1)$出解。时间复杂度$O(nsqrt{n})$。

对于$s_k<sqrt{n}$的串，考虑用一遍$dfs$计算每个节点对经过他的串的贡献，用分块/树状数组维护前缀和。

代码：

#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N = 100050;
template<typename T>
inline void read(T&x)
{
    T f = 1,c = 0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
    x = f*c;
}
ll n,m,rt[N];
ll len[N];
char mp[N];
struct BIT
{
    ll id[N];
    ll tag[N],s[350];
    void init()
    {
        for(ll i=1;i<=n;i++)id[i]=i/300+1;
    }
    void up(ll x,ll d)
    {
        for(ll i=x;id[i]==id[x];i++)tag[i]+=d;
        for(ll i=id[x]+1;i<=id[n];i++)s[i]+=d;
    }
    ll down(ll x){return tag[x]+s[id[x]];}
}bt;
ll hed[N],cnt;
struct EG
{
    ll to,nxt;
}e[N];
void ae(ll f,ll t)
{
    e[++cnt].to = t;
    e[cnt].nxt = hed[f];
    hed[f] = cnt;
}
ll ans[N];
struct Q
{
    ll l,r,id;
    Q(){}
    Q(ll l,ll r,ll i):l(l),r(r),id(i){}
};
vector<Q>v3[N];
vector<ll>v1[N],v2[N];
struct Trie
{
    ll tot,ch[N][26],fa[N],fl[N];
    void insert(ll l,ll k)
    {
        ll u = 0;
        for(ll i=1;i<=l;i++)
        {
            ll c = mp[i]-'a';
            if(!ch[u][c])ch[u][c]=++tot,fa[tot]=u;
            u = ch[u][c];
            if(l*l<=n)v1[u].push_back(k);
        }
        v2[u].push_back(k);
        rt[k] = u;
    }
    void build()
    {
        queue<ll>q;
        for(ll i=0;i<26;i++)
            if(ch[0][i])
            {
                q.push(ch[0][i]);
                ae(0,ch[0][i]);
            }
        while(!q.empty())
        {
            ll u = q.front();
            q.pop();
            for(ll i=0;i<26;i++)
            {
                ll &v = ch[u][i];
                if(!v)
                {
                    v = ch[fl[u]][i];
                    continue;
                }
                fl[v] = ch[fl[u]][i];
                ae(fl[v],v);
                q.push(v);
            }
        }
    }
}tr;
ll s[N],w[N];
void dfs1(ll u)
{
    for(ll j=hed[u];j;j=e[j].nxt)
    {
        ll to = e[j].to;
        dfs1(to);
        w[u]+=w[to];
    }
    for(ll i=0,lim=(ll)v2[u].size();i<lim;i++)
        s[v2[u][i]]=w[u];
}
void sol1()
{
    for(ll i=1;i<=n;i++)if(len[i]*len[i]>n)
    {
        memset(s,0,sizeof(s));
        memset(w,0,sizeof(w));
        for(ll j=rt[i];j;j=tr.fa[j])
            w[j]=1;
        dfs1(0);
        for(ll j=1;j<=n;j++)
            s[j]+=s[j-1];
        for(ll j=0,lim=(ll)v3[i].size();j<lim;j++)
            ans[v3[i][j].id] = s[v3[i][j].r] - s[v3[i][j].l-1];
    }
}
void dfs2(ll u)
{
    for(ll j=0,lim=(ll)v2[u].size();j<lim;j++)
        bt.up(v2[u][j],1);
    for(ll j=0,lim=(ll)v1[u].size();j<lim;j++)
    {
        ll v = v1[u][j];
        for(ll i=0,lm=(ll)v3[v].size();i<lm;i++)
            ans[v3[v][i].id]+=bt.down(v3[v][i].r)-bt.down(v3[v][i].l-1);
    }
    for(ll j=hed[u];j;j=e[j].nxt)
        dfs2(e[j].to);
    for(ll j=0,lim=(ll)v2[u].size();j<lim;j++)bt.up(v2[u][j],-1);
}
int main()
{
//    freopen("tt.in","r",stdin);
    read(n),read(m);
    bt.init();
    for(ll i=1;i<=n;i++)
    {
        scanf("%s",mp+1);
        len[i] = strlen(mp+1);
        tr.insert(len[i],i);
    }
    tr.build();
    for(ll l,r,k,i=1;i<=m;i++)
    {
        read(l),read(r),read(k);
        v3[k].push_back(Q(l,r,i));
    }
    sol1();
    dfs2(0);
    for(ll i=1;i<=m;i++)
        printf("%I64d
",ans[i]);
    return 0;
}