In mathematics you don't understand things, you just get used to them.

Description

Link.

给定字符串,正整数集合 $A,B$,满足 $\forall u\in A,v\in B,1\le u,v\le n$。

求 $\sum_{i\in A}\sum_{j\in B}\text{LCP}(A,B)$。

Solution

双倍经验是 SvT,只不过 SvT 这屑玩意儿卡常。

先反转串,然后插入 SAM。众所周知

把字符串反转后插入 SAM 后,两个原串的后缀在 parent tree 上的 $\text{LCA}$ 是这两个后缀的 $\text{LCP}$。

然后你就可以搞两个 DP,分别跑 $A$ 子树大小,$B$ 子树大小。

注意根节点需要特殊处理,因为我们是跨子树跑的 DP。不过 SvT 不需要,不知道是不是我的问题(应该就是)。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m,dfn[500010],fa[500010][21],dep[500010],sjc,pos[200010],onepower[500010],anopower[500010],onef[500010],anof[500010];
char s[200010];
LL ans;
struct SuffixAutomaton
{
    #define ID(c) ((c)-'a')
    vector<int> e[500010];
    int n,cntot,las,len[500010],pre[500010],ch[500010][26];
    char s[200010];
    void init(int _n,char c[])
    {
        n=_n;
        for(int i=1;i<=n;++i)    s[i]=c[i];
        cntot=las=1;
    }
    void extend(char c)
    {
        int cur=++cntot,one=las,ano=0;
        len[cur]=len[las]+1,las=cur;
        while(one&&!ch[one][ID(c)])    ch[one][ID(c)]=cur,one=pre[one];
        if(one==0)    pre[cur]=1;
        else
        {
            ano=ch[one][ID(c)];
            if(len[one]+1==len[ano])    pre[cur]=ano;
            else
            {
                int clone=++cntot;
                len[clone]=len[one]+1;
                pre[clone]=pre[ano];
                memcpy(ch[clone],ch[ano],sizeof(ch[ano]));
                while(one&&ch[one][ID(c)]==ano)    ch[one][ID(c)]=clone,one=pre[one];
                pre[ano]=pre[cur]=clone;
            }
        }
    }
    void build()
    {
        for(int i=1;i<=n;++i)    extend(s[i]),pos[i]=las;
        for(int i=2;i<=cntot;++i)    e[pre[i]].emplace_back(i);
    }
}SAM;
void dfs(int x,int las)
{
    dfn[x]=++sjc,fa[x][0]=las,dep[x]=dep[las]+1;
    for(int i=1;i^21;++i)    fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int y : SAM.e[x])    dfs(y,x);
}
int LCA(int one,int ano)
{
    if(dep[one]<dep[ano])    swap(one,ano);
    for(int i=20;~i;--i)    if(dep[fa[one][i]]>=dep[ano])    one=fa[one][i];
    if(one^ano)
    {
        for(int i=20;~i;--i)    if(fa[one][i]^fa[ano][i])    one=fa[one][i],ano=fa[ano][i];
        return fa[one][0];
    }
    else    return one;
}
bool cmp(int one,int ano){return dfn[one]<dfn[ano];}
struct VirtualTree
{
    vector<int> e[500010];
    vector<int> build(vector<int> poi)
    {
        sort(poi.begin(),poi.end(),cmp);
        poi.erase(unique(poi.begin(),poi.end()),poi.end());
        int len=poi.size();
        for(int i=1;i<len;++i)    poi.push_back(LCA(poi[i-1],poi[i]));
        sort(poi.begin(),poi.end(),cmp);
        poi.erase(unique(poi.begin(),poi.end()),poi.end());
        len=poi.size();
        for(int i=1;i<len;++i)    e[LCA(poi[i-1],poi[i])].push_back(poi[i]);
        return poi;
    }
}VRT;
template<class T>
void read(T &hhh)
{
    T x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')    f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')    x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
    if(~f)    hhh=x;
    else    hhh=-x;
}
template<class T>
void write(T x,char las='\n')
{
    static int st[100],top=0;
    if(x<0)    putchar('-'),x=-x;
    do st[++top]=x%10,x/=10; while(x);
    while(top)    putchar(st[top--]^'0');
    putchar(las);
}
void exdfs(int x)
{
    for(int y : VRT.e[x])    exdfs(y),onef[x]+=onef[y],anof[x]+=anof[y];
    for(int y : VRT.e[x])    ans+=(LL)SAM.len[x]*(onef[x]-onef[y])*anof[y];
    ans+=(LL)((onepower[x]&anopower[x])+onepower[x]*anof[x]+anopower[x]*onef[x])*SAM.len[x];
    onef[x]+=onepower[x],anof[x]+=anopower[x];
}
int main()
{
    read(n),read(m);
    scanf("%s",s+1);
    reverse(s+1,s+n+1);
    SAM.init(n,s),SAM.build();
    dfs(1,0);
    while(m--)
    {
        int ones,anos,x;
        read(ones),read(anos);
        vector<int> key,tmp;
        while(ones--)    read(x),key.push_back(pos[n-x+1]),onepower[pos[n-x+1]]=1;
        while(anos--)    read(x),key.push_back(pos[n-x+1]),anopower[pos[n-x+1]]=1;
        tmp=VRT.build(key);
        ans=0,exdfs(tmp[0]);
        write(ans);
        for(int now : tmp)    onef[now]=anof[now]=0,VRT.e[now].clear(),onepower[now]=anopower[now]=0;
    }
    return 0;
}

dp strings suffix structures

Solution -「BZOJ 3779」重组病毒
上一篇 «
Note -「virtual tree」shorter vrt
» 下一篇