「2025 杭电多校 2」1004. 子串的故事(2)

    「2025 杭电多校 2」1004. 子串的故事(2)

    HDU 7994

    对于一个包含字符串 s1,s2,…,sks_1, s_2, \dots, s_k 的字符串可重集 TT,定义 TT 的价值为

    ∑1≤i<j≤kLCP(si,sj)\sum\limits_{1 \leq i < j \leq k} \mathrm{LCP}(s_i, s_j)

    给出一个长度为 nn 的字符串 SS,下标从 11 到 nn。有一个初始为空的字符串集合 TT。

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

    每次操作过后,你都需要求出此刻集合 TT 的价值。答案对 109+710^9 + 7 取模。

    数据范围:1≤n,m≤1051 \leq n, m \leq 10^5。

    时空限制:88s / 512512MiB。

    Solution

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

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

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

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

    设 n,mn, m 同阶,时间复杂度 O(nlog⁡2n)\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;
    }
    
    /**
     *  心中无女人
     *  比赛自然神
     *  模板第一页
     *  忘掉心上人
    **/

    在线版的代码就不放了 …