「2025 杭电多校 2」1004. 子串的故事（2）

发表于 2025-09-04 分类于杭电多校本文字数： 1.7k 阅读时长 ≈ 6 分钟

Description

对于一个包含字符串 $s_1, s_2, \cdots, s_k$ 的字符串可重集 $T$ ，定义 $T$ 的价值为

\sum\limits_{1 \leq i < j \leq k} \mathrm{LCP}(s_i, s_j)

给出一个长度为 $n$ 的字符串 $S$ ，下标从 $1$ 到 $n$ 。有一个初始为空的字符串集合 $T$ 。

有 $m$ 次操作，每次操作给出两个正整数 $l, r(1 \leq l \leq r \leq n)$ ，你需要将字符串 $S[l : r]$ 的所有前缀都加入集合 $T$ 。形式化地，对于所有 $l \leq i \leq r$ ，你需要将 $S[l : i]$ 加入集合 $T$ 。

每次操作过后，你都需要求出此刻集合 $T$ 的价值。答案对 $10^9 + 7$ 取模。

数据范围： $1 \leq n, m \leq 10^5$ 。

时空限制： $8$ s / $512$ MiB。

~~我不会告诉你，这个题是我出的。~~

Solution

考虑一个最简单的想法：建出后缀 trie，则两个子串 $s_1, s_2$ 的 $\mathrm{LCP}$ 就转化为了 $\mathrm{dep}[\mathrm{LCA}(p_1, p_2)]$ 。可以套用 [LNOI2014] LCA 的 trick。但本题是要将一个字符串的所有前缀都加入，则相当于是链加等差数列，链乘等差数列求和。维护区间的 $0/1/2$ 次项之和即可。

进一步优化，建出反串的 SAM。对于 SAM 上的每个节点，维护深度在 $\mathrm{minl} \sim \mathrm{maxl}$ 的辅助数组 $a$ 信息。但注意到，询问串在 SAM 上的状态可能不完全覆盖 $\mathrm{minl} \sim \mathrm{maxl}$ （为该区间的一个前缀）。

记录一个 SAM 上离线拆节点的 trick：离线将所有询问子串在 SAM 上的状态找出来，然后将状态划分，建立有关询问串的虚拟节点（补充有关询问串的虚树结构）。此时所有询问串一定完整地覆盖从当前状态到根的路径，且总节点数不超过 $2n + m$ 。

还有一个粗暴的想法是：不新建节点，只不过对于不完全覆盖时多算或少算的贡献，还要进行打补丁。

设 $n, m$ 同阶，时间复杂度 $\mathcal{O}(n \log^2 n)$ 。

#include <bits/stdc++.h>

using s64 = long long;

template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

/* ----- ----- ----- 正文 ----- ----- ----- */

const int N = 100100, M = 100100;
const int NewN = N * 2 + M;

const int mod = 1e9 + 7;

int n, m;
std::string str;

struct Graph {
    std::vector< std::vector<int> > table;

    void init(int _n) {
        table.assign(_n + 1, {});
    }

    void add_edge(int u, int v) {
        table[u].push_back(v);
    }
} G;

int ptr;
int minl[NewN], maxl[NewN];

namespace SAM {
    const int SIZE = N * 2;

    int NodeCount, Last;
    struct node {
        int trans[26];
        int link, maxl;
    } t[SIZE];

    std::vector<int> son[SIZE];
    int anc[18][SIZE];

    int create() {
        int p = ++ NodeCount;
        for (int c = 0; c < 26; c ++) {
            t[p].trans[c] = 0;
        }
        t[p].link = t[p].maxl = 0;
        return p;
    }

    void init() {
        NodeCount = 0, Last = create();
    }

    int location[N];

    std::map<int, int> buc[SIZE];

    void extend(int c, int i) {
        int p = Last,
            np = Last = create();
        
        t[np].maxl = t[p].maxl + 1;

        for (; p && t[p].trans[c] == 0; p = t[p].link) {
            t[p].trans[c] = np;
        }

        if (!p) {
            t[np].link = 1;
        } else {
            int q = t[p].trans[c];

            if (t[q].maxl == t[p].maxl + 1) {
                t[np].link = q;
            } else {
                int nq = ++ NodeCount; t[nq] = t[q];
                t[nq].maxl = t[p].maxl + 1;

                t[np].link = t[q].link = nq;

                for (; p && t[p].trans[c] == q; p = t[p].link) {
                    t[p].trans[c] = nq;
                }
            }
        }

        location[i] = np;
    }

    void build_tree() {
        for (int i = 1; i <= NodeCount; i ++) {
            son[i].clear();
            buc[i].clear();
        }
        for (int i = 2; i <= NodeCount; i ++) {
            son[t[i].link].push_back(i);
        }

        for (int i = 1; i <= NodeCount; i ++) {
            buc[i][t[i].maxl] = 1;
            anc[0][i] = t[i].link;
        }
        for (int j = 1; j <= 17; j ++) {
            for (int i = 1; i <= NodeCount; i ++) {
                anc[j][i] = anc[j - 1][anc[j - 1][i]];
            }
        }
    }

    /* 子串定位 */
    int find(int l, int r) {
        int p = location[l];
        for (int i = 17; i >= 0; i --) {
            if (t[anc[i][p]].maxl >= r - l + 1) {
                p = anc[i][p];
            }
        }
        return p;
    }

    void dfs(int u, int fu) {
        for (auto &[L, p] : buc[u]) {
            p = ++ ptr;
            minl[p] = maxl[fu] + 1, maxl[p] = L;

            G.add_edge(fu, p);
            fu = p;
        }

        for (int v : son[u]) {
            dfs(v, fu);
        }
    }

    void build_newtree() {
        G.init(2 * n + m);

        ptr = 0;
        dfs(1, 0);
    }
}

std::pair<int, int> range[M];

int match[M];

int dep[NewN], sze[NewN], Fa[NewN], son[NewN];

void dfs1(int u, int fu) {
    dep[u] = dep[fu] + 1;
    sze[u] = 1;

    Fa[u] = fu;
    son[u] = 0;

    for (int v : G.table[u]) {
        dfs1(v, u);

        sze[u] += sze[v];
        if (sze[v] > sze[son[u]]) {
            son[u] = v;
        }
    }
}

int dfsClock, dfn[NewN], idx[NewN];
int Top[NewN];

void dfs2(int u, int P) {
    dfsClock ++;
    dfn[u] = dfsClock, idx[dfsClock] = u;

    Top[u] = P;

    if (son[u]) dfs2(son[u], P);
    for (int v : G.table[u]) {
        if (v == son[u]) continue;
        dfs2(v, v);
    }
}

int f1(int n) {
    return (1ll * n * (n + 1) / 2) % mod;
}
int f1(int l, int r) {
    return f1(r) - f1(l - 1);
}

int f2(int n) {
    return (1ll * n * (n + 1) * (2 * n + 1) / 6) % mod;
}
int f2(int l, int r) {
    return f2(r) - f2(l - 1);
}

int g(int n) {
    return (1ll * n * (n + 1) * (n - 1) / 6) % mod;
}

namespace SGT {
    struct node {
        int l, r;
        int s1, s2;
        int addk, addb;
        void mk_add(int k, int b) {
            int L = minl[idx[l]], R = maxl[idx[r]];
            s1 = (s1 + 1ll * k * f1(L, R) + 1ll * b * (R - L + 1)) % mod;
            s2 = (s2 + 1ll * k * f2(L, R) + 1ll * b * f1(L, R)) % mod;
            addk = (addk + k) % mod, addb = (addb + b) % mod;
        }
    } t[NewN * 4];

    void upd(int p) {
        t[p].s1 = (t[p * 2].s1 + t[p * 2 + 1].s1) % mod;
        t[p].s2 = (t[p * 2].s2 + t[p * 2 + 1].s2) % mod;
    }

    void spread(int p) {
        if (!t[p].addk && !t[p].addb) return;
        t[p * 2].mk_add(t[p].addk, t[p].addb), t[p * 2 + 1].mk_add(t[p].addk, t[p].addb);
        t[p].addk = t[p].addb = 0;
    }

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r, t[p].s1 = t[p].s2 = t[p].addk = t[p].addb = 0;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
    }

    void addRange(int p, int s, int e, int k, int b) {
        if (s <= t[p].l && t[p].r <= e) {
            t[p].mk_add(k, b);
            return;
        }
        spread(p);
        int mid = (t[p].l + t[p].r) >> 1;
        if (s <= mid) {
            addRange(p * 2, s, e, k, b);
        }
        if (mid < e) {
            addRange(p * 2 + 1, s, e, k, b);
        }
        upd(p);
    }

    int ask1(int p, int s, int e) {
        if (s <= t[p].l && t[p].r <= e) {
            return t[p].s1;
        }
        spread(p);
        int mid = (t[p].l + t[p].r) >> 1;
        if (s <= mid && mid < e) {
            return (ask1(p * 2, s, e) + ask1(p * 2 + 1, s, e)) % mod;
        }
        if (s <= mid) {
            return ask1(p * 2, s, e);
        } else {
            return ask1(p * 2 + 1, s, e);
        }
    }
    int ask2(int p, int s, int e) {
        if (s <= t[p].l && t[p].r <= e) {
            return t[p].s2;
        }
        spread(p);
        int mid = (t[p].l + t[p].r) >> 1;
        if (s <= mid && mid < e) {
            return (ask2(p * 2, s, e) + ask2(p * 2 + 1, s, e)) % mod;
        }
        if (s <= mid) {
            return ask2(p * 2, s, e);
        } else {
            return ask2(p * 2 + 1, s, e);
        }
    }
}

int ans;

void solve(int p) {
    int x, s1 = 0, s2 = 0;

    x = p;
    while (x) {
        s1 = (s1 + SGT::ask1(1, dfn[Top[x]], dfn[x])) % mod;
        s2 = (s2 + SGT::ask2(1, dfn[Top[x]], dfn[x])) % mod;
        x = Fa[Top[x]];
    }

    ans = (ans + 1ll * (maxl[p] + 1) * s1) % mod;
    ans = (ans - s2) % mod;

    x = p;
    while (x) {
        SGT::addRange(1, dfn[Top[x]], dfn[x], -1, maxl[p] + 1);
        x = Fa[Top[x]];
    }
}

void work() {   
    std::cin >> n >> m;
    std::cin >> str, str = " " + str;

    SAM::init();
    for (int i = n; i >= 1; i --) {
        SAM::extend(str[i] - 'a', i);
    }

    SAM::build_tree();

    for (int i = 1; i <= m; i ++) {
        int l, r;
        std::cin >> l >> r;

        range[i] = {l, r};

        int p = SAM::find(l, r);

        SAM::buc[p][r - l + 1] = 1;
        match[i] = p;
    }

    SAM::build_newtree();

    dfsClock = 0;
    dfs1(1, 0);
    dfs2(1, 1);

    SGT::build(1, 1, dfsClock);

    ans = 0;
    for (int i = 1; i <= m; i ++) {
        auto [l, r] = range[i];

        solve(SAM::buc[match[i]][r - l + 1]);

        ans = (ans + g(r - l + 1)) % mod;

        ans = (ans + mod) % mod;
        std::cout << ans << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int T;
    std::cin >> T;

    while (T --) {
        work();
    }
    
    return 0;
}

/**
 *  心中无女人
 *  比赛自然神
 *  模板第一页
 *  忘掉心上人
**/

在线版的代码就不放了 …