CF1073G. Yet Another LCP Problem

选两组后缀$s,t$,求$\sum lcp(s_i,t_j)$

检验板子题

• 字符串反转插入后缀自动机就是后缀树，记录下每个后缀的终止节点。
• $lcp(i,j)$=$maxlen[lca(i,j)]$
• 非常简单的树形$dp$，注意$i=j$的情况即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 8e5 + 10;
const int mod = 1e9 + 7;

int read()
{
    int 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 << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
const int SN = 4e5 + 10;
const int SM = 26;
struct SAM
{
    int trans[SN][SM], link[SN], pre, scnt, len[SN], siz[SN];
    SAM() { pre = scnt = 1; }

    void insert(int id)
    {
        int cur = ++scnt;
        siz[cur] = 1;
        len[cur] = len[pre] + 1;
        int u;

        for (u = pre; u && !trans[u][id]; u = link[u])
            trans[u][id] = cur;
        pre = cur;
        if (!u)
            link[cur] = 1;
        else
        {
            int x = trans[u][id];
            if (len[u] + 1 == len[x])
                link[cur] = x;
            else
            {
                int nc = ++scnt;
                link[nc] = link[x];
                len[nc] = len[u] + 1;
                memcpy(trans[nc], trans[x], sizeof(trans[x]));
                link[cur] = link[x] = nc;
                for (; u && trans[u][id] == x; u = link[u])
                    trans[u][id] = nc;
            }
        }
    }
} sam;
namespace Tree
{

    int st[N][22], dfn[N], dep[N], tot, lg2[N];
    vector<int> G[N];
    void dfs(int x, int fa)
    {
        st[++tot][0] = x;
        dep[x] = dep[fa] + 1;
        dfn[x] = tot;
        for (int to : G[x])
        {
            if (to == fa)
                continue;
            dfs(to, x);
            st[++tot][0] = x;
        }
    }
    int lower(int u, int v)
    {
        return (dep[u] < dep[v]) ? u : v;
    }

    void Lca_init()
    {
        dfs(1, 0);
        for (int i = 2; i <= tot; i++)
            lg2[i] = lg2[i >> 1] + 1;
        for (int l = 1; (1 << l) <= tot; l++)
        {
            for (int i = 1; i + (1 << l) - 1 <= tot; i++)
                st[i][l] = lower(st[i][l - 1], st[i + (1 << (l - 1))][l - 1]);
        }
    }
    int lca(int u, int v)
    {
        u = dfn[u];
        v = dfn[v];
        if (u > v)
            swap(u, v);
        int i = lg2[v - u + 1], w = (1 << i);
        return lower(st[u][i], st[v - w + 1][i]);
    }
    int dis(int u, int v)
    {
        int lc = lca(u, v);
        return dep[u] + dep[v] - 2 * dep[lc];
    }
}; // namespace Tree
using namespace Tree;

namespace XTree
{
    stack<int> s;
    vector<int> tmp;
    int dp[N][2];
    int b[N];
    int vis1[N], vis0[N];
    ll ans;
    vector<pii> g[N];

    bool cmp(int x, int y)
    {
        return Tree::dfn[x] < Tree::dfn[y];
    }

    void addEdge(int u, int v)
    {
        int d = Tree::dis(u, v);

        g[u].push_back(mk(v, d));
        g[v].push_back(mk(u, d));
    }

    void build(int k)
    {

        tmp.clear();
        while (!s.empty())
            s.pop();
        sort(b + 1, b + 1 + k, cmp);
        k = unique(b + 1, b + 1 + k) - b - 1;
        s.push(1);
        tmp.push_back(1);
        for (int i = 1; i <= k; ++i)
        {
            int x = b[i];
            tmp.push_back(x);
            int lca = Tree::lca(x, s.top());
            while (s.top() != lca)
            {
                int tmc = s.top();
                s.pop();
                if (dfn[s.top()] < dfn[lca])
                    s.push(lca), tmp.push_back(lca);
                addEdge(s.top(), tmc);
            }
            s.push(x);
        }
        while (s.top() != 1)
        {
            int tmp = s.top();
            s.pop();
            addEdge(s.top(), tmp);
        }
    }
    void clear()
    {
        for (int x : tmp)
        {
            g[x].clear();
            dp[x][1] = dp[x][0] = 0;
        }
    }
    void dfs1(int x, int fa, int d)
    {
        ll res = 0;

        for (pii now : g[x])
        {
            int to = now.first;
            int w = now.second;
            if (to == fa)
                continue;

            dfs1(to, x, d + w);
            if (vis0[x] != 0)
            {
                res += dp[to][1];
            }
            if (vis1[x] != 0)
            {
                res += dp[to][0];
            }

            res += 1ll * dp[to][1] * dp[x][0];
            res += 1ll * dp[x][1] * dp[to][0];

            dp[x][0] += dp[to][0];
            dp[x][1] += dp[to][1];
        }
        if (vis0[x] != 0)
            dp[x][0] += 1;
        if (vis1[x] != 0)
            dp[x][1] += 1;

        ans += sam.len[x] * res;
    }
    void solve()
    {

        dfs1(1, 0, 0);
        cout << ans << endl;
    }

} // namespace XTree

char s[N];
int ed[N];
int main()
{
    int n = read(), q = read();
    scanf("%s", s + 1);
    reverse(1 + s, 1 + s + n);
    for (int i = 1; i <= n; i++)
    {
        sam.insert(s[i] - 'a');
        ed[i] = sam.pre;
    }
    reverse(1 + ed, 1 + ed + n);

    for (int i = 2; i <= sam.scnt; i++)
    {
        G[sam.link[i]].push_back(i);
    }
    Tree::Lca_init();

    for (int i = 1; i <= q; i++)
    {
        int A = read(), B = read();
        int cnt = 0;
        XTree::ans = 0;
        for (int j = 1; j <= A; j++)
        {
            int x = read();
            x = ed[x];
            XTree::vis1[x] = 1;
            XTree::b[++cnt] = x;
        }
        for (int j = 1; j <= B; j++)
        {
            int x = read();
            int tmp = x;
            x = ed[x];
            if (XTree::vis1[x])
                XTree::ans += n - tmp + 1;
            XTree::vis0[x] = 1;
            XTree::b[++cnt] = x;
        }
        XTree::build(cnt);
        XTree::solve();
        XTree::clear();
        for (int j = 1; j <= cnt; j++)
            XTree::vis1[XTree::b[j]] = 0, XTree::vis0[XTree::b[j]] = 0;
    }
}