BZOJ 3879 SvT

有趣的 Suffix virtual Tree。

显然对询问的后缀建虚树即可……

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5e5;
const int M = 3e6;
const long long mod = 23333333333333333;
int n,m,t;
char s[N + 5];
int pos[N + 5];
long long ans;
namespace SAM
{
    struct node
    {
        int ch[26];
        int fa,len;
    } sam[(N << 1) + 5];
    int las = 1,tot = 1;
    inline void insert(int x)
    {
        int cur = las,p = ++tot;
        sam[p].len = sam[cur].len + 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        las = p;
    }
    int to[(N << 1) + 5],pre[(N << 1) + 5],first[(N << 1) + 5];
    inline void add(int u,int v)
    {
        static int tot = 0;
        to[++tot] = v,pre[tot] = first[u],first[u] = tot;
    }
    int dep[(N << 1) + 5],sz[(N << 1) + 5],son[(N << 1) + 5],top[(N << 1) + 5],id[(N << 1) + 5],rk[(N << 1) + 5];
    void dfs(int p)
    {
        static int tot = 0;
        sz[rk[id[p] = ++tot] = p] = 1;
        for(register int i = first[p];i;i = pre[i])
            dep[to[i]] = dep[p] + 1,
            dfs(to[i]),
            sz[p] += sz[to[i]],
            son[p] = max(son[p],to[i],[](int x,int y)
            {
                return sz[x] < sz[y];
            });
    }
    inline void build()
    {
        for(register int i = 2;i <= tot;++i)
            add(sam[i].fa,i);
        dfs(1);
        for(register int i = 1;i <= tot;++i)
            top[rk[i]] = rk[i] == son[sam[rk[i]].fa] ? top[sam[rk[i]].fa] : rk[i];
    }
    inline int getlca(int x,int y)
    {
        while(top[x] ^ top[y])
            dep[top[x]] > dep[top[y]] ? (x = sam[top[x]].fa) : (y = sam[top[y]].fa);
        return dep[x] < dep[y] ? x : y;
    }
}
namespace VT
{
    int to[(N << 1) + 5],pre[(N << 1) + 5],first[(N << 1) + 5],edge_tot;
    inline void add(int u,int v)
    {
        int &tot = edge_tot;
        to[++tot] = v,pre[tot] = first[u],first[u] = tot;
    }
    int sz[(N << 1) + 5];
    int key[M + 5],tot;
    int s[(N << 1) + 5],top;
    inline void build()
    {
        sort(key + 1,key + tot + 1,[](int x,int y)
        {
            return SAM::id[x] < SAM::id[y];
        }),tot = unique(key + 1,key + tot + 1) - key - 1;
        top = edge_tot = 0,first[s[++top] = 1] = sz[1] = 0;
        for(register int i = 1,lca;i <= tot;++i)
        {
            if(key[i] ^ 1)
            {
                lca = SAM::getlca(key[i],s[top]);
                if(lca ^ s[top])
                {
                    for(;SAM::id[lca] < SAM::id[s[top - 1]];add(s[top - 1],s[top]),--top);
                    if(SAM::id[lca] > SAM::id[s[top - 1]])
                        first[lca] = sz[lca] = 0,add(lca,s[top]),s[top] = lca;
                    else
                        add(lca,s[top--]);
                }
                first[s[++top] = key[i]] = 0;
            }
            sz[key[i]] = 1;
        }
        for(;top > 1;add(s[top - 1],s[top]),--top);
        --top;
    }
    void dfs(int p)
    {
        for(register int i = first[p];i;i = pre[i])
            dfs(to[i]),
            ans = (ans + (long long)SAM::sam[p].len * sz[p] % mod * sz[to[i]]) % mod,
            sz[p] += sz[to[i]];
    }
}
int main()
{
    scanf("%d%d%s",&n,&m,s + 1);
    for(register int i = n;i;--i)
        SAM::insert(s[i] - 'a'),pos[i] = SAM::las;
    SAM::build();
    for(;m;--m)
    {
        scanf("%d",&t),VT::tot = ans = 0;
        for(int x;t;--t)
            scanf("%d",&x),VT::key[++VT::tot] = pos[x];
        VT::build(),VT::dfs(1);
        printf("%lld\n",ans);
    }
}