P4384:「八省联考2018」制胡窜 – 题解

主要思路

看完题面就知道应该又是传统的字符串重工题，最后写了我 6.3KB。

首先建出 SAM 然后处理倍增+线段树维护 endpos 集合是显然需要的。然后开始考虑这个二元组的含义。

想了一段时间如何正着算，发现这个东西成立的条件是或，所以正着算只能用子集容斥。所以我们考虑把条件进行反转，变成强与形式，然后用所有的二元组的数量 \( {n – 1 \choose 2} \) 来减掉即可。

如何算正好不符合条件的二元组数量呢？分两种情况讨论：

• 最左区间和最右区间相交
• 最左区间和最右区间不相交

第一种情况

考虑左端点 \(i\) 的选取：

• 在 \([1, l_1)\) 区间内，我们必须要用右端点 \(j\) 去劈断第一个串，所以答案就是 \((l_1 – 1)(r_1 – l_m)\)。
• 在 \([l_i, l_{i + 1})\) 时，我们需要 \(j\) 劈断后面所有的串，所以必须要在 \(r_{i + 1}\) 左侧且 \(l_m\) 右侧才行。也就是：\( \sum_{i = 1}^{m – 1} (l_{i + 1} – l_i)(r_{i + 1} – l_m)) \)
• 在 \([l_m, r_1)\) 时，我们这个时候啥都劈断了，有 \(i + 1 < j\) 即可。
• \([r_1, n]\) 时，显然啥都劈不断，所以没贡献。

第二种情况

跟上面差不多，需要注意一些奇怪的性质即可。

代码

// P4384.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200, INF = 0x7fffffff;

int n, q, pos[MAX_N], roots[MAX_N];
char str[MAX_N];

typedef long long ll;

namespace SegmentTree
{

    struct node
    {
        int max_val, min_val;
        ll sum[2];
        void clear() { max_val = min_val = sum[0] = sum[1] = 0; }
    } nodes[MAX_N * 40];

    int ptot, lson[MAX_N * 30], rson[MAX_N * 30];

    node pushup(node ls, node rs)
    {
        node ret;
        ret.clear();
        ret.max_val = max(ls.max_val, rs.max_val);
        ret.min_val = min(ls.min_val, rs.min_val);
        ret.sum[0] = ls.sum[0] + rs.sum[0] + 1LL * rs.min_val * (rs.min_val - ls.max_val);
        ret.sum[1] = ls.sum[1] + rs.sum[1] + rs.min_val - ls.max_val;
        return ret;
    }

#define mid ((l + r) >> 1)

    int queryMax(int ql, int qr, int l, int r, int p)
    {
        if (p == 0)
            return 0;
        if (ql <= l && r <= qr)
            return nodes[p].max_val;
        int ret = 0;
        if (ql <= mid)
            ret = max(ret, queryMax(ql, qr, l, mid, lson[p]));
        if (mid < qr)
            ret = max(ret, queryMax(ql, qr, mid + 1, r, rson[p]));
        return ret;
    }

    int queryMin(int ql, int qr, int l, int r, int p)
    {
        if (p == 0)
            return INF;
        if (ql <= l && r <= qr)
            return nodes[p].min_val;
        int ret = INF;
        if (ql <= mid)
            ret = min(ret, queryMin(ql, qr, l, mid, lson[p]));
        if (mid < qr)
            ret = min(ret, queryMin(ql, qr, mid + 1, r, rson[p]));
        return ret;
    }

    void query(int ql, int qr, int l, int r, int p, node &ret)
    {
        if (p == 0)
            return;
        if (ql <= l && r <= qr)
        {
            if (ret.min_val == 0)
                ret = nodes[p];
            else
                ret = pushup(ret, nodes[p]);
            return;
        }
        if (ql <= mid)
            query(ql, qr, l, mid, lson[p], ret);
        if (mid < qr)
            query(ql, qr, mid + 1, r, rson[p], ret);
    }

    int update(int qx, int l, int r, int p)
    {
        if (p == 0)
            p = ++ptot;
        if (l == r)
        {
            nodes[p].max_val = qx, nodes[p].min_val = qx;
            nodes[p].sum[0] = nodes[p].sum[1] = 0;
            return p;
        }
        if (qx <= mid)
            lson[p] = update(qx, l, mid, lson[p]);
        else
            rson[p] = update(qx, mid + 1, r, rson[p]);
        if (lson[p] && rson[p])
            nodes[p] = pushup(nodes[lson[p]], nodes[rson[p]]);
        else if (lson[p])
            nodes[p] = nodes[lson[p]];
        else
            nodes[p] = nodes[rson[p]];
        return p;
    }

    int merge(int x, int y)
    {
        if (x == 0 || y == 0)
            return x + y;
        int p = ++ptot;
        lson[p] = merge(lson[x], lson[y]);
        rson[p] = merge(rson[x], rson[y]);
        if (lson[p] && rson[p])
            nodes[p] = pushup(nodes[lson[p]], nodes[rson[p]]);
        else
            nodes[p] = lson[p] ? nodes[lson[p]] : nodes[rson[p]];
        return p;
    }

#undef mid

} // namespace SegmentTree

namespace SAM
{

    struct node
    {
        int ch[10], link, dep;
    } nodes[MAX_N];

    int ptot = 1, last_ptr = 1, up[20][MAX_N], bucket[MAX_N], idx[MAX_N];

    void insert(int c)
    {
        int pre = last_ptr, p = last_ptr = ++ptot;
        nodes[p].dep = nodes[pre].dep + 1;
        while (pre && nodes[pre].ch[c] == 0)
            nodes[pre].ch[c] = p, pre = nodes[pre].link;
        if (pre == 0)
            nodes[p].link = 1;
        else
        {
            int q = nodes[pre].ch[c];
            if (nodes[q].dep == nodes[pre].dep + 1)
                nodes[p].link = q;
            else
            {
                int clone = ++ptot;
                nodes[clone] = nodes[q], nodes[clone].dep = nodes[pre].dep + 1;
                nodes[p].link = nodes[q].link = clone;
                while (pre && nodes[pre].ch[c] == q)
                    nodes[pre].ch[c] = clone, pre = nodes[pre].link;
            }
        }
    }

    void radixSort()
    {
        for (int i = 1; i <= ptot; i++)
            bucket[nodes[i].dep]++;
        for (int i = 1; i <= ptot; i++)
            bucket[i] += bucket[i - 1];
        for (int i = 1; i <= ptot; i++)
            idx[bucket[nodes[i].dep]--] = i;
        for (int i = 2; i <= ptot; i++)
            up[0][i] = nodes[i].link;
        for (int i = ptot; i >= 2; i--)
            roots[nodes[idx[i]].link] =
                SegmentTree::merge(roots[nodes[idx[i]].link], roots[idx[i]]);
        for (int i = 1; i < 20; i++)
            for (int j = 1; j <= ptot; j++)
                up[i][j] = up[i - 1][up[i - 1][j]];
    }

    int jump(int l, int r)
    {
        int p = pos[r];
        for (int i = 19; i >= 0; i--)
            if (nodes[up[i][p]].dep >= (r - l + 1))
                p = up[i][p];
        return p;
    }

} // namespace SAM

ll binomial2(int n) { return (1LL * n * (n - 1)) >> 1; }

ll query(int l, int r)
{
    int p = SAM::jump(l, r), len = r - l + 1;
    int lft = SegmentTree::nodes[roots[p]].min_val;
    int rig = SegmentTree::nodes[roots[p]].max_val;
    if (lft < rig - (len << 1) + 1 && SegmentTree::queryMax(lft, rig - len, 1, n, roots[p]) - len + 1 > lft)
        return binomial2(n - 1);
    if (rig - len + 1 <= lft)
    {
        SegmentTree::node rnd = SegmentTree::nodes[roots[p]];
        int lm = rig - len + 1;
        ll ret = rnd.sum[0] - rnd.sum[1] * lm + binomial2(lft - lm) + 1LL * (lft - lm) * (n - len);
        return binomial2(n - 1) - ret;
    }
    else
    {
        SegmentTree::node rnd;
        rnd.clear();
        int lm = rig - len + 1, poslm = SegmentTree::queryMax(1, lm, 1, n, roots[p]);
        SegmentTree::query(poslm, lft + len - 1, 1, n, roots[p], rnd);
        int p1 = SegmentTree::queryMax(1, lft + len - 1, 1, n, roots[p]);
        int p2 = SegmentTree::queryMin(lft + len, n, 1, n, roots[p]);
        ll ret = rnd.sum[0] - rnd.sum[1] * lm + (p2 > lm ? 1LL * (lft - (p1 - len + 1)) * (p2 - lm) : 0);
        return binomial2(n - 1) - ret;
    }
}

int main()
{
    scanf("%d%d%s", &n, &q, str + 1);
    for (int i = 1; i <= n; i++)
    {
        SAM::insert(str[i] - '0'), pos[i] = SAM::last_ptr;
        roots[pos[i]] = SegmentTree::update(i, 1, n, roots[pos[i]]);
    }
    SAM::radixSort();
    while (q--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%lld\n", query(l, r));
    }
    return 0;
}