2022 年牛客多校加赛场 C 题题解

C Cmostp

题意：给定字符串 $SS$，$qq$ 次询问 $SS$ 的全部本质不同子串中有多少个子串的右端点落入 $[l,r][l,r]$ 中的。 $\mathrm{\mid }S\mathrm{\mid },q\le 5\times 10^5|S|,q\; \backslash leq\; 5\backslash times\; 10^5$。

解法：显然在 SAM 上可以将前缀 $[1,i][1,i]$ 对应节点在扩展的时候找到，记该节点为 $d_{i}d\_i$。同时每个节点对应了 $ll$ 个本质不同子串。那么问题转化为，$\mathrm{\forall }k\in [l,r]\backslash forall\; k\; \backslash in\; [l,r]$，$d_{k}d\_k$ 到根节点的全部链的并上节点的 $ll$ 之和。这是由于 $d_{k}d\_k$ 对应的这些串的 endpos 必然有元素 $kk$，那么它所有 link 树上的父亲的 endpos 集合都必然有元素 $kk$，因而都需要计入该次询问。

考虑根据 $rr$ 从小到大的离线询问，对 link 树进行树链剖分。依次插入第 $ii$ 个终止节点，首先使用树链剖分将 $ii$ 到根节点的链找到，并对链上的全部点染色成当前的 $ii$（即进行 Access 操作），这样做的目的在于更新每个 link 树上节点 endpos 集合中小于等于 $ii$ 的最大值，而显然能更新的只有从 $d_{i}d\_i$ 节点沿 link 树上的全部祖先，因为只有这些节点的 endpos 集合中有 $ii$。

该步骤可以通过树链剖分+区间合并线段树完成。对于每个线段树上节点，维护它所对应链的左侧颜色和右侧颜色，以及最靠右（对应于树上的更深侧）的颜色变化点 div（即从这里开始颜色发生变化），那么这个信息非常容易区间合并。同时同步的使用树状数组维护前面的 $jj$ 条链现在的长度 $w_{j}w\_j$（即颜色为 $jj$ 的点的 $ll$ 之和），那么对于固定 $rr$ 的全部询问 $[l,r][l,r]$，答案就是 ${\displaystyle \sum _{k=l}^r{w}_k}\backslash displaystyle\; \backslash sum\_\{k=l\}^r\; w\_k$。

因而总的时间复杂度为 $\mathcal{O}(n{}^{2}n)\backslash mathcal\; O(n\backslash log^2n)$。

#include <bits/stdc++.h>
using namespace std;
class BIT
{
    vector<int> t;
    int n;
    int lowbit(int x)
    {
        return x & (-x);
    }
    long long query(int x)
    {
        long long ans = 0;
        while (x)
        {
            ans += t[x];
            x -= lowbit(x);
        }
        return ans;
    }

public:
    void set(int n)
    {
        this->n = n;
        t.resize(n + 1);
    }
    void update(int x, int k)
    {
        while (x <= n)
        {
            t[x] += k;
            x += lowbit(x);
        }
    }
    long long query(int l, int r)
    {
        return query(r) - query(l - 1);
    }
};
struct node
{
    int leftcol, rightcol;
    int left, right;
    int div;
    int tag;
    node()
    {
        left = right = leftcol = rightcol = div = tag = 0;
    }
    node(int _left, int _right, int _leftcol, int _rightcol)
    {
        left = _left;
        right = _right;
        leftcol = _leftcol;
        rightcol = _rightcol;
        div = tag = 0;
    }
    node operator+(const node b) const
    {
        node ans(left, b.right, leftcol, b.rightcol);
        if (b.div)
            ans.div = b.div;
        else if (rightcol != b.leftcol)
            ans.div = right;
        else if (div)
            ans.div = div;
        return ans;
    }
};
struct query
{
    int id;
    int l, r;
    query(int _id, int _l, int _r)
    {
        l = _l;
        r = _r;
        id = _id;
    }
    bool operator<(const query &b) const
    {
        return r < b.r;
    }
};
class segment_tree
{

    vector<node> t;
    int n;
    void pushdown(int place, int left, int right)
    {
        if (t[place].tag)
        {
            int mid = (left + right) >> 1;
            update(place << 1, left, mid, left, mid, t[place].tag);
            update(place << 1 | 1, mid + 1, right, mid + 1, right, t[place].tag);
            t[place].tag = 0;
        }
    }
    void update(int place, int left, int right, int start, int end, int x)
    {
        if (start <= left && right <= end)
        {
            t[place].div = 0;
            t[place].leftcol = t[place].rightcol = x;
            t[place].tag = x;
            return;
        }
        pushdown(place, left, right);
        int mid = (left + right) >> 1;
        if (start <= mid)
            update(place << 1, left, mid, start, end, x);
        if (end > mid)
            update(place << 1 | 1, mid + 1, right, start, end, x);
        t[place] = t[place << 1] + t[place << 1 | 1];
    }
    void build(int place, int left, int right)
    {
        t[place] = node(left, right, 0, 0);
        if (left == right)
            return;
        int mid = (left + right) >> 1;
        build(place << 1, left, mid);
        build(place << 1 | 1, mid + 1, right);
    }
    node query(int place, int left, int right, int start, int end)
    {
        if (start <= left && right <= end)
            return t[place];
        pushdown(place, left, right);
        int mid = (left + right) >> 1;
        if (end <= mid)
            return query(place << 1, left, mid, start, end);
        if (start > mid)
            return query(place << 1 | 1, mid + 1, right, start, end);
        return query(place << 1, left, mid, start, end) + query(place << 1 | 1, mid + 1, right, start, end);
    }

public:
    void set(int n)
    {
        this->t.resize(4 * n + 5);
        this->n = n;
        build(1, 1, n);
    }
    void update(int l, int r, int col)
    {
        update(1, 1, n, l, r, col);
    }
    node query(int l, int r)
    {
        return query(1, 1, n, l, r);
    }
};
class Tree_Split
{
    vector<vector<int>> graph;
    BIT num_edge;
    segment_tree t;
    vector<int> maxson, siz, father, tp, id, val, revid;
    int ind;
    void dfs1(int place, int fa)
    {
        father[place] = fa;
        siz[place] = 1;
        for (auto i : graph[place])
            if (i != fa)
            {
                dfs1(i, place);
                siz[place] += siz[i];
                if (!maxson[place] || siz[maxson[place]] < siz[i])
                    maxson[place] = i;
            }
    }
    void dfs2(int place, int ancestor)
    {
        id[place] = ++ind;
        revid[ind] = place;
        tp[place] = ancestor;
        if (maxson[place])
            dfs2(maxson[place], ancestor);
        for (auto i : graph[place])
            if (i != father[place] && i != maxson[place])
                dfs2(i, i);
    }

public:
    Tree_Split(vector<vector<int>> &graph, vector<int> &status_len, int m)
    {
        int n = graph.size() - 1;
        ind = 0;
        num_edge.set(m);
        this->graph = graph;
        val = status_len;
        tp.resize(n + 1);
        id.resize(n + 1);
        revid.resize(n + 1);
        maxson.resize(n + 1);
        siz.resize(n + 1);
        father.resize(n + 1);
        dfs1(1, 0);
        dfs2(1, 1);
        t.set(n);
    }
    void access(int x, int col)
    {
        if (col == 1)
        {
            num_edge.update(1, val[x]);
            while (x)
            {
                t.update(id[tp[x]], id[x], col);
                x = father[tp[x]];
            }
        }
        else
        {
            while(x)
            {
                int ori = x;
                while(1)
                {
                    node temp = t.query(id[tp[x]], id[ori]);
                    int div = temp.div;
                    if(!div)
                        div = tp[x];
                    else
                        div = revid[div + 1];
                    if(temp.rightcol)
                        num_edge.update(temp.rightcol, val[father[div]] - val[ori]);
                    num_edge.update(col, val[ori] - val[father[div]]);
                    if (div == tp[x])
                        break;
                    ori = father[div];
                }
                t.update(id[tp[x]], id[x], col);
                x = father[tp[x]];

            }
        }
    }
    long long query(int l, int r)
    {
        return num_edge.query(l, r);
    }
};
class SAM
{
    const int shift = 97;
    struct node
    {
        int ch[26];
        int len;
        int father;
        node()
        {
            memset(ch, 0, sizeof(ch));
            len = father = 0;
        }
    } NIL;
    vector<node> t;
    int last, ind;
    int insert(int c)
    {
        int p = last;
        int np = last = ++ind;
        t.push_back(NIL);
        t[np].len = t[p].len + 1;
        for (; p && !t[p].ch[c]; p = t[p].father)
            t[p].ch[c] = np;
        if (!p)
            t[np].father = 1;
        else
        {
            int q = t[p].ch[c];
            if (t[p].len + 1 == t[q].len)
                t[np].father = q;
            else
            {
                int nq = ++ind;
                t.push_back(t[q]);
                t[nq].len = t[p].len + 1;
                t[q].father = t[np].father = nq;
                for (; p && t[p].ch[c] == q; p = t[p].father)
                    t[p].ch[c] = nq;
            }
        }
        return last;
    }
    vector<int> pos;
    vector<vector<int>> graph;

public:
    SAM(string s)
    {
        last = ind = 1;
        t.push_back(NIL);
        t.push_back(NIL);
        for (auto i : s)
            pos.push_back(insert(i - shift));
        graph.resize(t.size());
        for (int i = 2; i <= ind; i++)
            graph[t[i].father].push_back(i);
    }
    vector<long long> solve(vector<query> &que)
    {
        vector<int> len(t.size());
        for (int i = 1; i <= ind;i++)
            len[i] = t[i].len;
        int n = pos.size(), q = que.size(), place = 0;
        sort(que.begin(), que.end());
        vector<long long> ans(q);
        Tree_Split tr(graph, len, n);
        for (int i = 0; i < n; i++)
        {
            tr.access(pos[i], i + 1);
            while (place < q && que[place].r == i + 1)
            {
                ans[que[place].id] = tr.query(que[place].l, que[place].r);
                place++;
            }
        }
        return ans;
    }
};
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin.tie(NULL);
    cout.tie(NULL);
    string s;
    int n, q;
    cin >> n >> q >> s;
    SAM solve(s);
    vector<query> que;
    for (int i = 0, l, r; i < q;i++)
    {
        cin >> l >> r;
        que.emplace_back(i, l, r);
    }
    for (auto i : solve.solve(que))
        cout << i << "\n";
    return 0;
}