E. Data Structures Fan - 题解

比赛与标签

比赛: Codeforces Round 895 (Div. 3) 标签: binary search, bitmasks, data structures, dp 难度: *1500

题目大意喵~

主人，这道题是这样的呐：

我们有一个整数数组 a 和一个只包含 '0' 和 '1' 的字符串 s，它们的长度都是 n。然后呢，我们需要处理 q 个查询。

查询有两种类型哦：

类型 1 (1 l r): 给定一个区间 [l, r]，我们需要把字符串 s 在这个区间里的所有字符都翻转一下！也就是说，'0' 变成 '1'，'1' 变成 '0'。
类型 2 (2 g): 给定一个数字 g（g 只会是 0 或者 1），我们需要计算所有满足 s[i] == g 的位置 i 上对应的 a[i] 的异或和。如果一个满足条件的位置都没有，那异或和就是 0 啦。

我们的任务就是快速又准确地回答所有类型 2 的查询，喵~

解题思路 Nyan-alysis!

这道题的核心在于“区间修改”和“全局查询”，一看到这个组合，聪明的猫娘我呀，脑海里立刻就浮现出了线段树的身影！

为啥呢？让本喵来分析一下：

朴素做法的瓶颈：如果每次查询都老老实实地遍历，类型 1 的修改需要 O(r-l+1) 的时间，类型 2 的查询需要 O(n) 的时间。在 n 和 q 都高达 10^5 的情况下，O(n*q) 的总复杂度肯定会超时的说。
线段树的优势：线段树最擅长的就是处理区间问题了！它可以把区间操作的复杂度从 O(n) 优化到 O(log n)。
如何设计线段树节点？
- 我们需要查询 s[i] == '0' 对应的 a[i] 的异或和，以及 s[i] == '1' 对应的 a[i] 的异或和。
- 所以，我们的线段树节点可以设计成这样：每个节点 v 维护它所代表的区间 [tl, tr] 内的两部分信息：
  - x0: 区间内所有 s[i] == '0' 的 a[i] 的异或和。
  - x1: 区间内所有 s[i] == '1' 的 a[i] 的异或和。
- 父节点的 x0 就是它两个子节点的 x0 的异或和，x1 也是同理。查询 g=0 或 g=1 的全局异或和，就直接取根节点的 x0 或 x1 就好啦，这是 O(1) 的操作！
最关键的区间修改！
- 当我们要对区间 [l, r] 进行翻转操作时，这意味着在这个区间里，原来 s[i] == '0' 的地方现在变成了 s[i] == '1'，反之亦然。
- 这会发生什么奇妙的事情呢？对于线段树中任何一个完全包含于 [l, r] 的节点 v，它所维护的 x0 和 x1 应该互相交换！因为原来对 x0 有贡献的 a[i] 现在都跑去给 x1 做贡献了，反之亦然。
- 这是一个超级棒的性质！我们不需要一个一个去修改叶子节点，只需要在对应的区间节点上交换 x0 和 x1 就行了。
懒惰标记 (Lazy Propagation) 的引入
- 为了实现高效的区间修改，我们需要引入懒惰标记。当一个修改操作完全覆盖了某个节点代表的区间时，我们就在这个节点上打上一个 lazy 标记，并交换它的 x0 和 x1，然后就停下，不再继续往下递归。
- 这个 lazy 标记的意思是：“嘿，我这个节点下面的子树都需要翻转哦，但是我先懒一下，等下次有查询或修改需要经过我这里时，我再把这个翻转任务传递给我的孩子们~”。
- 当我们访问一个带有 lazy 标记的节点时，我们就需要先“下推”这个标记：把它子节点的 lazy 标记也翻转一下，并交换它们子节点的 x0 和 x1，然后清除自己的 lazy 标记。

总结一下我们的策略就是：

建树: O(n) 遍历一遍 a 和 s，初始化好每个叶子节点的 x0 和 x1，然后向上合并。
修改: O(log n) 在线段树上进行区间更新，利用懒惰标记和 swap(x0, x1)。
查询: O(1) 直接取根节点的 x0 或 x1。

这样一来，总复杂度就是 O(n + q * log n)，完全可以接受啦！是不是很优雅呢，喵~

代码实现 Purrfect Code!

cpp

// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// 线段树的节点结构，喵~
struct Node {
    long long x0; // 维护区间内 s[i] == '0' 对应的 a[i] 的异或和
    long long x1; // 维护区间内 s[i] == '1' 对应的 a[i] 的异或和
    bool lazy;    // 懒惰标记，true 表示这个区间需要翻转
};

vector<Node> tree; // 我们的线段树本体

// 下推懒惰标记的函数，把爸爸的懒惰传递给孩子们
void push(int v, int tl, int tr) {
    // 如果当前节点没有懒惰标记，就啥也不用做
    if (tree[v].lazy) {
        // 如果不是叶子节点，就把标记传给左右子节点
        if (tl != tr) {
            int left = 2 * v + 1;
            int right = 2 * v + 2;
            
            // 交换左子节点的 x0 和 x1，并翻转它的懒惰标记
            swap(tree[left].x0, tree[left].x1);
            tree[left].lazy = !tree[left].lazy;
            
            // 交换右子节点的 x0 和 x1，并翻转它的懒惰标记
            swap(tree[right].x0, tree[right].x1);
            tree[right].lazy = !tree[right].lazy;
        }
        // 自己的任务完成了，清除标记
        tree[v].lazy = false;
    }
}

// 构建线段树的函数，从无到有建立我们的数据结构
void build(int v, int tl, int tr, vector<long long>& a, string& s) {
    tree[v].lazy = false; // 初始化时没有懒惰标记
    if (tl == tr) { // 到达叶子节点
        if (s[tl] == '0') {
            tree[v].x0 = a[tl];
            tree[v].x1 = 0;
        } else {
            tree[v].x0 = 0;
            tree[v].x1 = a[tl];
        }
        return;
    }
    // 递归构建左右子树
    int tm = (tl + tr) / 2;
    build(2 * v + 1, tl, tm, a, s);
    build(2 * v + 2, tm + 1, tr, a, s);
    
    // 从子节点合并信息到当前节点
    tree[v].x0 = tree[2 * v + 1].x0 ^ tree[2 * v + 2].x0;
    tree[v].x1 = tree[2 * v + 1].x1 ^ tree[2 * v + 2].x1;
}

// 区间更新函数，实现 s 字符串的区间翻转
void update(int v, int tl, int tr, int l, int r) {
    // 如果更新区间无效，直接返回
    if (l > r) 
        return;
    
    // 如果当前节点代表的区间被更新区间完全覆盖
    if (tl == l && tr == r) {
        // 交换 x0 和 x1，并打上懒惰标记
        swap(tree[v].x0, tree[v].x1);
        tree[v].lazy = !tree[v].lazy;
        return;
    }
    
    // 在深入子节点之前，先下推懒惰标记
    push(v, tl, tr);
    
    int tm = (tl + tr) / 2;
    // 递归更新左右子树中与 [l, r] 有交集的部分
    update(2 * v + 1, tl, tm, l, min(r, tm));
    update(2 * v + 2, tm + 1, tr, max(l, tm + 1), r);
    
    // 更新完子节点后，重新计算当前节点的值
    tree[v].x0 = tree[2 * v + 1].x0 ^ tree[2 * v + 2].x0;
    tree[v].x1 = tree[2 * v + 1].x1 ^ tree[2 * v + 2].x1;
}

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        string s;
        cin >> s;
        int q;
        cin >> q;

        // 为每个测试用例重新分配和构建线段树
        tree.assign(4 * n, {0, 0, false});
        build(0, 0, n - 1, a, s);

        vector<long long> ans;
        for (int i = 0; i < q; i++) {
            int type;
            cin >> type;
            if (type == 1) {
                int l, r;
                cin >> l >> r;
                // 注意题目给的是 1-based index，我们要转成 0-based
                update(0, 0, n - 1, l - 1, r - 1);
            } else {
                int g;
                cin >> g;
                // 查询操作直接取根节点的值，O(1) 的说！
                if (g == 0) {
                    ans.push_back(tree[0].x0);
                } else {
                    ans.push_back(tree[0].x1);
                }
            }
        }

        // 统一输出答案
        for (int i = 0; i < (int)ans.size(); i++) {
            cout << ans[i] << (i == (int)ans.size() - 1 ? "" : " ");
        }
        cout << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度: O(N + Q * logN) 的说。
- build 函数需要访问每个节点一次来构建线段树，所以是 O(N)。
- update 函数每次操作最多访问 O(logN) 个节点，因为线段树的高度是 O(logN)。进行 Q 次查询，这部分就是 O(Q * logN)。
- 类型 2 的查询是 O(1)，因为它只需要访问根节点。
- 所以总的时间复杂度是 O(N + Q * logN)，非常高效！
空间复杂度: O(N) 的说。
- 我们需要一个大小约为 4 * N 的数组来存储线段树，所以空间是线性的，O(N)。

知识点与总结

这道题真是一道非常经典的线段树教学题呢，喵~ 通过它我们可以学到：

线段树的核心思想: 将区间问题分治，用树形结构来维护区间信息，从而实现快速的区间操作。
懒惰标记 (Lazy Propagation): 这是处理区间修改的灵魂！当修改操作影响一大片连续的叶子节点时，懒惰标记可以避免我们深入到每一个叶子，大大提高了效率。
问题转化与抽象: 本题最巧妙的地方在于将“翻转二进制位”这个操作，抽象成了“交换两个异或和”的代数操作。找到了这个对应关系，问题就迎刃而解了。
异或(XOR)的性质: 异或满足交换律和结合律，这是我们能在线段树中合并区间异或和的基础。a ^ b = b ^ a，(a ^ b) ^ c = a ^ (b ^ c)。

希望本猫娘的讲解能帮助到主人哦！以后遇到类似的“区间修改，全局/区间查询”问题，一定要想起可爱的线段树呀！加油，喵~！

E. Data Structures Fan - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路 Nyan-alysis! ​

代码实现 Purrfect Code! ​

复杂度分析 ​

知识点与总结 ​