Moe's CF Life

Appearance

D. Distinct Characters Queries - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 590 (Div. 3) 标签: data structures 难度: *1600

题目大意喵~ ​

主人你好呀！这次的任务是关于一个可爱的字符串 s 的说！(ฅ'ω'ฅ)

我们有两种操作需要处理：

  1. 修改操作: 1 pos c，意思是把字符串 s 在第 pos 个位置的字符换成新的字符 c。
  2. 查询操作: 2 l r，意思是问你，在字符串 s 从第 l 个位置到第 r 个位置的这段子串里，一共有多少种不同的字符呢？

比如说，如果子串是 "abacaba"，那么不同的字符有 'a', 'b', 'c'，一共 3 种。如果子串是 "bbbb"，那就只有 'b' 这一种字符啦！

我们需要快速地响应 q 次这样的操作，并且对每一次查询操作，都给出正确的答案，喵~

解题思路，喵！ ​

看到这种又要有单点修改，又要有区间查询的问题，我的猫猫雷达立刻就响了！这不就是为线段树量身定做的舞台嘛，的说！(๑•̀ㅂ•́)و✧

但是，线gao段树要维护什么信息呢？我们要查询的是区间内不同字符的种类数。

一个最朴素的想法是，每个线段树节点存一个 std::set 或者 std::unordered_set 来记录它所代表的区间里有哪些字符。合并的时候就把两个子节点的集合合并一下。但是这样太慢啦！每次合并都要花费不少时间，肯定会超时的说。

这时候，就要用上一个超级巧妙的技巧——位掩码 (Bitmask)！

我们知道，小写字母一共只有 26 个，这个数字非常小，对吧？这是一个关键的突破口，喵！我们可以用一个 32 位的整数（int 就够啦）来表示一个字符集合。这个整数的二进制表示中，从右往左数第 0 位代表 'a'，第 1 位代表 'b'，...，第 25 位代表 'z'。

  • 如果某一位是 1，就表示对应的字符在这个集合里。
  • 如果某一位是 0，就表示对应的字符不在。

举个例子呐：

  • 字符串 "ac" 的字符集合是 {'a', 'c'}。对应的位掩码就是 (1 << 0) | (1 << 2)，也就是二进制的 ...00101，十进制的 1 + 4 = 5。
  • 字符串 "b" 的字符集合是 {'b'}。对应的位掩码就是 (1 << 1)，也就是二进制的 ...00010，十进制的 2。

用位掩码有什么好处呢？

  1. 合并信息超快：想要求两个区间的字符集合的并集，只需要把它们的位掩码做一次按位或 (OR, |) 操作就可以了！mask_parent = mask_left | mask_right。这可比合并 set 快太多了！
  2. 查询结果方便：查询一个区间的不同字符数，就等于查询完得到的最终位掩码里，有多少个 1。这个操作也有一个专门的内置函数 __builtin_popcount() 可以瞬间完成！

所以我们的策略就清晰啦：

  1. 建立线段树:
    • 线段树的每个节点都存储一个 int，表示该节点对应区间内所有不同字符的位掩码。
    • 叶子节点: 对于字符串 s 的第 i 个字符 s[i]，它对应的叶子节点的位掩码就是 1 << (s[i] - 'a')。
    • 非叶子节点: 它的位掩码等于它两个子节点位掩码的按位或结果。
  2. 处理修改操作 1 pos c:
    • 这是一个单点更新。我们从根节点出发，找到代表位置 pos 的那个叶子节点。
    • 把这个叶子节点的值更新为新字符 c 的位掩码，即 1 << (c - 'a')。
    • 然后回溯，沿途更新所有父节点的值（用 OR 操作重新计算）。
  3. 处理查询操作 2 l r:
    • 这是一个区间查询。我们在线段树上查询 [l, r] 这个区间的合并位掩码。
    • 得到最终的位掩码 mask 后，调用 __builtin_popcount(mask) 计算出 1 的个数，就是答案啦！

这个方法把复杂的问题转换成了高效的位运算，是不是很优雅呢？喵~

代码实现，上菜咯！ ​

cpp
#include <iostream>
#include <vector>
#include <string>
 // 使用 __builtin_popcount 是因为它在 GNU G++ 中非常高效，喵~
// 在 C++20 及之后版本，也可以用 <bit> 里的 std::popcount 哦！
#define popcount __builtin_popcount

// 全局变量，存放我们的字符串和线段树的说
std::string s;
std::vector<int> tree;
int n;

// Function to build the segment tree from the initial string.
// 每个节点存储它对应区间内所有字符的位掩码
void build(int node, int start, int end) {
    if (start == end) {
        // 叶子节点：位掩码只代表一个字符
        tree[node] = (1 << (s[start - 1] - 'a'));
        return;
    }
    int mid = start + (end - start) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    // 内部节点：用按位或操作合并左右子节点的字符集合
    tree[node] = tree[2 * node] | tree[2 * node + 1];
}

// Function to update a character at a given 1-based position 'idx' to 'val'.
// 在位置 idx (1-based) 更新字符为 val
void update(int node, int start, int end, int idx, char val) {
    if (start == end) {
        // 找到啦！这就是要更新的叶子节点，设置新的字符掩码
        tree[node] = (1 << (val - 'a'));
        return;
    }
    int mid = start + (end - start) / 2;
    if (idx <= mid) {
        // 要更新的位置在左子树
        update(2 * node, start, mid, idx, val);
    } else {
        // 要更新的位置在右子树
        update(2 * node + 1, mid + 1, end, idx, val);
    }
    // 子节点更新完后，记得把父节点也更新一下哦！
    tree[node] = tree[2 * node] | tree[2 * node + 1];
}

// Function to query for the bitmask of distinct characters in a range [l, r].
// 查询区间 [l, r] 内所有不同字符的位掩码
int query(int node, int start, int end, int l, int r) {
    // 如果当前节点的区间和查询区间完全没有交集，
    // 返回 0，因为 0 是按位或的单位元，不影响结果
    if (r < start || end < l) {
        return 0;
    }
    // 如果当前节点的区间完全被查询区间覆盖，
    // 直接返回当前节点预先算好的位掩码
    if (l <= start && end <= r) {
        return tree[node];
    }
    // 否则，当前区间和查询区间部分重叠，需要分别查询左右子节点
    int mid = start + (end - start) / 2;
    int p1 = query(2 * node, start, mid, l, r);
    int p2 = query(2 * node + 1, mid + 1, end, l, r);
    // 把左右子节点的结果合并起来，就是当前层的答案
    return p1 | p2;
}

int main() {
    // 加速输入输出，让程序跑得飞快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> s;
    n = s.length();

    // 线段树一般需要 4*n 的空间才安全，这里用 4*n+1，因为我们是从节点 1 开始的
    tree.resize(4 * n + 1);
    build(1, 1, n);

    int q;
    std::cin >> q;
    while (q--) {
        int type;
        std::cin >> type;
        if (type == 1) {
            int pos;
            char c;
            std::cin >> pos >> c;
            update(1, 1, n, pos, c);
        } else {
            int l, r;
            std::cin >> l >> r;
            // 1. 查询得到区间的合并位掩码
            int mask = query(1, 1, n, l, r);
            // 2. 计算位掩码中 1 的个数，就是不同字符的数量啦！
            std::cout << popcount(mask) << "\n";
        }
    }

    return 0;
}

复杂度分析 ​

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

    • build 函数初始化线段树，需要遍历每个节点一次，所以是 O(N)，其中 N 是字符串的长度。
    • update 和 query 操作，每次都是从根节点走到一个叶子节点或者遍历部分分支，树的高度是 O(log N)，所以每次操作的时间复杂度是 O(log N)。
    • 总共有 Q 次查询，所以总时间复杂度就是 O(N + Q * log N)，对于这道题的 N 和 Q 都是 10^5 的数据量来说，是完全可以接受的！

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

    • 我们主要的空间开销就是线段树 tree 数组，它的大小大约是 4N，所以空间复杂度是 O(N)。

知识点与总结 ​

这次的冒险旅程让我们学会了几个非常厉害的魔法呢，喵~

  1. 线段树 (Segment Tree): 它是处理区间问题的大杀器！只要你想做的操作满足结合律（比如加法、乘法、最大值、按位或），就可以用线段树来优化。
  2. 位掩码 (Bitmask): 当要处理的元素种类数量很少（比如本题的 26 个字母）时，位掩码是一个超级棒的工具。它能把集合操作（比如求并集）变成极快的位运算，大大提升效率。
  3. __builtin_popcount(): 这个 GCC/Clang 内置函数是数二进制位中 1 的个数的神器，比自己手写循环快得多！在比赛中一定要记得用它哦。

核心思想总结: 当遇到“区间内不同元素的个数”这类问题，并且元素总类的数量不大时，“线段树 + 位掩码” 是一个经典且高效的组合拳！

希望这篇题解能帮到主人你哦！继续加油，你一定能成为最棒的算法大师，喵！🐾

Released under the MIT License.

Copyright © 2024-present Moe