E. William The Oblivious - 题解

比赛与标签

比赛: Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2) 标签: bitmasks, data structures, dp, matrices 难度: *2400

题目大意喵~

主人你好呀~！这道题是这样的呐：

我们有一个长度为 n 的字符串，里面只包含 'a', 'b', 'c' 三种字符。接下来会有 q 次操作。每次操作会把字符串某个位置的字符换成一个新的字符。

在每次操作之后，我们都需要回答一个问题：最少需要修改多少个字符，才能让这个字符串里不包含 "abc" 作为它的子序列？

举个例子，"axbyc" 包含 "abc" 子序列，但 "acb" 就不包含啦。我们要计算的就是达成这个目标的最小修改次数~

解题思路的奇妙旅程

喵~ 看到这种“区间修改”和“查询”，是不是立刻就想到了我们可爱又强大的线段树呀？没错！这道题的核心就是用线段树来解决一个动态规划（DP）问题，这种技巧也被称为“DP on segment tree”，非常厉害的说！

为什么要用线段树？

因为题目有单点修改，而且每次修改后都要查询整个字符串的全局答案。如果每次都暴力跑一遍 DP（O(N)），那 q 次查询下来就是 O(N*Q)，肯定会超时的说。线段树可以将修改和查询的复杂度都降到 O(log N)，完美解决问题！

线段树节点里要存什么信息呢？

这是最关键的一步！为了计算整个区间的答案，我们需要知道它的左右子区间的一些信息，然后通过这些信息合并（combine）出父区间的答案。

我们最终要求的是**“最少修改次数，使得字符串不含 'abc' 子序列”**。让我们把它记作 cost(S, "abc")。

为了计算 cost(L+R, "abc")，其中 L 和 R 是左右子区间，一个 "abc" 子序列的来源可能是：

1. a, b, c 全部在 L 中。
2. a, b, c 全部在 R 中。
3. a 在 L 中，b 和 c 在 R 中。
4. a 和 b 在 L 中，c 在 R 中。

要阻止所有这些情况，我们需要一些子问题的答案。这就启发我们，一个线段树节点需要存储以下信息：

• a, b, c: 分别表示该区间内 'a', 'b', 'c' 字符的数量。这个数量也恰好是把这个区间内所有 'a' (或 'b', 'c') 都修改掉的成本！
• ab: 表示使该区间不含 "ab" 子序列的最小修改次数。
• bc: 表示使该区间不含 "bc" 子序列的最小修改次数。
• abc: 表示使该区间不含 "abc" 子序列的最小修改次数。这个就是我们最终想要的答案！

神奇的 combine 合并操作

假设我们有两个相邻的区间，左边是 l，右边是 r。我们要把它们的信息合并到父节点 res 中。

1. res.a, res.b, res.c: 这个最简单啦，直接把左右区间的数量加起来就好。 res.a = l.a + r.a; (b 和 c 同理)

2. res.ab: 如何让 l+r 这个新区间不含 "ab" 子序列？

   • 策略一：把 l 区间里的 'a' 全都改掉（成本 l.a），并且保证 r 区间本身不含 "ab"（成本 r.ab）。这样 'a' 就不可能从 l 跑出来了。
   • 策略二：保证 l 区间本身不含 "ab"（成本 l.ab），并且把 r 区间里的 'b' 全都改掉（成本 r.b）。这样 'b' 就不可能从 r 跑出来了。
   • 我们取这两种策略中成本更小的那个，喵~ res.ab = min(l.a + r.ab, l.ab + r.b);

3. res.bc: 和 ab 的道理一模一样！ res.bc = min(l.b + r.bc, l.bc + r.c);

4. res.abc: 这是最核心的部分！如何让 l+r 不含 "abc"？

   • 策略一：把 l 区间里的 'a' 全都改掉（成本 l.a），并且保证 r 区间不含 "abc"（成本 r.abc）。
   • 策略二：保证 l 区间不含 "abc"（成本 l.abc），并且把 r 区间里的 'c' 全都改掉（成本 r.c）。
   • 策略三（最巧妙的!）：保证 l 区间不含 "ab"（成本 l.ab），并且保证 r 区间不含 "bc"（成本 r.bc）。这样，a 和 b 无法同时出现在 l，b 和 c 无法同时出现在 r，就成功把 a...b...c 的链条在中间切断了！
   • 我们取这三种策略中成本最小的那个~ res.abc = min({ l.abc + r.c, l.a + r.abc, l.ab + r.bc });

叶子节点和更新

• 叶子节点 (build): 当区间长度为 1 时，比如只包含一个字符 s[i]。它不可能构成 "ab", "bc", "abc" 子序列，所以 ab, bc, abc 的成本都是0。a, b, c 的成本就是看 s[i] 是哪个字符，对应的成本为1，其他为0。
• 更新 (update): 当一个点 pos 的字符改变时，我们从根节点往下找到对应的叶子节点，更新它的值，然后一路向上，用 combine 函数更新所有父节点的信息。

这样，每次更新后，根节点 tree[1] 的 abc 值就是整个字符串的全局答案啦！是不是很神奇的说？

代码实现喵~

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;

// 线段树节点结构体，存储我们DP需要的所有信息
struct Node {
    // a, b, c 分别是区间内对应字符的数量
    // 也代表了将区间内所有 a, b, c 字符修改掉的成本
    int a, b, c; 
    // ab, bc 分别是使区间不含 "ab" 或 "bc" 子序列的最小代价
    int ab, bc;
    // abc 是使区间不含 "abc" 子序列的最小代价，也是我们的最终目标
    int abc;
};

Node tree[4 * MAXN + 10];
string s;
int n, q;

// 合并左右子节点信息的核心函数
Node combine(const Node& l, const Node& r) {
    Node res;
    // 字符数直接相加
    res.a = l.a + r.a;
    res.b = l.b + r.b;
    res.c = l.c + r.c;

    // 计算不含 "ab" 的最小代价
    // 策略1: 左区间消灭'a' + 右区间不含"ab"
    // 策略2: 左区间不含"ab" + 右区间消灭'b'
    res.ab = min(l.a + r.ab, l.ab + r.b);

    // 计算不含 "bc" 的最小代价，逻辑同上
    res.bc = min(l.b + r.bc, l.bc + r.c);

    // 计算不含 "abc" 的最小代价
    // 策略1: 左区间消灭'a' + 右区间不含"abc"
    // 策略2: 左区间不含"abc" + 右区间消灭'c'
    // 策略3: 左区间不含"ab" + 右区间不含"bc" (在中间切断 a-b-c 链)
    res.abc = min({ l.abc + r.c, l.a + r.abc, l.ab + r.bc });
    
    return res;
}

// 构建线段树
void build(int idx, int l, int r) {
    if (l == r) { // 到达叶子节点
        tree[idx].a = (s[l] == 'a');
        tree[idx].b = (s[l] == 'b');
        tree[idx].c = (s[l] == 'c');
        // 单个字符无法构成"ab", "bc", "abc"，所以代价为0
        tree[idx].ab = 0;
        tree[idx].bc = 0;
        tree[idx].abc = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(idx * 2, l, mid); // 递归构建左子树
    build(idx * 2 + 1, mid + 1, r); // 递归构建右子树
    tree[idx] = combine(tree[idx*2], tree[idx*2+1]); // 合并左右子节点信息
}

// 单点更新
void update(int idx, int l, int r, int pos, char c) {
    if (l == r) { // 找到要更新的叶子节点
        s[l] = c; // 更新字符串（虽然这里不直接影响计算，但好习惯）
        tree[idx].a = (c == 'a');
        tree[idx].b = (c == 'b');
        tree[idx].c = (c == 'c');
        // ab, bc, abc 的代价依然是0
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) {
        update(idx * 2, l, mid, pos, c);
    } else {
        update(idx * 2 + 1, mid + 1, r, pos, c);
    }
    tree[idx] = combine(tree[idx*2], tree[idx*2+1]); // 向上更新父节点
}

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

    cin >> n >> q;
    cin >> s;

    build(1, 0, n-1); // 初始化建树

    for (int i = 0; i < q; i++) {
        int pos;
        char c;
        cin >> pos >> c;
        update(1, 0, n-1, pos-1, c); // 执行更新
        cout << tree[1].abc << '\n'; // 输出根节点的答案
    }

    return 0;
}

复杂度分析的说

• 时间复杂度: O(N + Q * log N) 的说。

  • build 函数构建整个线段树需要遍历所有 N 个元素，复杂度是 O(N)。
  • update 函数每次修改一个点，需要从根节点走到叶子节点，路径长度是 O(log N)，所以每次查询的复杂度是 O(log N)。总共有 Q 次查询，所以是 O(Q * log N)。
  • 加起来就是 O(N + Q * log N) 啦！

• 空间复杂度: O(N) 的说。

  • 线段树需要大约 4*N 的空间来存储所有节点，所以空间复杂度是 O(N)。

知识点与总结

这道题真是一次超棒的思维锻炼，呐！

1. 核心思想: 线段树 + 动态规划。当遇到序列上的动态修改和全局查询，并且查询的问题具有可合并的子结构时，就可以考虑这种强大的组合技！
2. DP状态设计: 解题的关键在于为线段树的节点设计出能覆盖所有情况的DP状态。我们不仅要存最终答案 abc 的成本，还要存储所有能推导出它的子问题，如 ab, bc 和 a, b, c 的成本。
3. 合并逻辑: combine 函数是DP的转移方程。理解三种策略如何覆盖所有 "abc" 的形成方式，是本题的精髓。
4. 从具体到抽象: 从“最少修改次数”这个问题，我们把它抽象成了“消除特定子序列的最小成本”，并用线段树的节点来维护这个成本，这个思维转换非常重要。

希望这篇题解能帮助你理解这道有趣的题目！继续加油，你也是算法大师喵~！