数据结构 - 题解

标签与难度

标签: 数据结构, 线段树, 排序, 懒标记, 区间修改, 值域线段树难度: 2100

题目大意喵~

你好呀，指挥官！这道题是这样的喵~

我们有一个长度为 $n$ 的正整数数列 $a_1, a_2, \dots, a_n$ 。接下来会有 $q$ 次操作。

每次操作会给我们三个整数 $l, r, c$ 。我们需要对数列 $a$ 里的每一个数 $a_i$ 进行检查：

它的值是否在 $[l, r]$ 这个区间内？
它的奇偶性是否和 $c$ 相同？（ $c=0$ 代表偶数， $c=1$ 代表奇数）

如果 $a_i$ 同时满足这两个条件，我们就要把它减 1，也就是 $a_i \leftarrow a_i - 1$ 。

在每次操作结束之后，我们需要计算当前整个数列所有数字的总和，然后用这个总和去更新一个答案变量。具体的更新方式是 ans ^= (i * current_sum)，其中 i 是第几次操作（从1开始）。最后输出这个最终的 ans 就好啦！

解题思路分析

喵哈哈，看到这道题，我的猫猫直觉告诉我，直接模拟肯定是不行的！ $n$ 和 $q$ 的规模都达到了 $5 \times 10^5$ ，如果每次操作都遍历整个数组，复杂度就是 $O(nq)$ ，这肯定会超时的说。所以，我们需要一个更高效的数据结构来处理这些操作，对吧？

关键的转化：从操作索引到操作值

我们来仔细看看操作的条件：a[i] 的值在 [l, r] 区间内。这个条件是针对数值的，而不是数组的下标。这种对值域进行操作的题目，有一个经典的处理技巧，那就是——先排序！

如果我们先把数组 a 从小到大排好序，那么数组的下标就和数值的大小有了直接的联系。比如说，排好序后，下标小的元素值也小，下标大的元素值也大。这样，我们就可以把对值域 [l, r] 的操作，转化为对一段连续下标的操作，这就很适合用线段树来维护了，喵~

线段树的设计

既然决定了用线段树，那我们就要想清楚线段树的每个节点需要维护哪些信息呢？

每次操作会改变元素的值（减1），并且这个改变会影响它的奇偶性。我们需要快速地找到符合条件的元素，并更新它们。所以，每个节点至少需要维护以下信息：

minValue, maxValue: 这个节点所代表的区间内，所有元素的最小值和最大值。这非常重要！它可以帮助我们快速判断一个区间内的所有元素是否都在查询的值域 [l, r] 内。
oddCount, evenCount: 这个区间内奇数和偶数的数量。因为操作的条件之一是奇偶性，所以这个信息是必不可少的。
lazyValue: 懒标记！既然是区间修改，懒标记就是我们的好朋友啦。这里我们用它来记录这个区间被累积减了多少。

操作流程详解

好嘞，准备工作都做好了，现在我们来梳理一下一次操作 (l, r, c) 的完整流程：

预处理:
- 读入数据，计算初始的总和 totalSum。
- 对数组 a 进行排序。
- 基于排好序的数组 a，构建我们的线段树。
执行修改: 我们从线段树的根节点开始，递归地进行修改。对于当前节点 u，我们有以下几种情况：
- 剪枝1 (完全不相干): 如果当前节点代表的值域 [u.minValue, u.maxValue] 和查询的值域 [l, r] 完全没有交集（即 u.maxValue < l 或 u.minValue > r），那么这个节点和它的子树都和本次操作无关，直接返回，喵~
- 剪枝2 (没有目标): 如果我们要修改的是奇数 (c=1)，但当前节点一个奇数都没有 (u.oddCount == 0)，那也不用继续下去了。偶数同理。
- 完全命中 (最理想的情况): 如果当前节点代表的值域 [u.minValue, u.maxValue] 完全被查询值域 [l, r] 覆盖（即 l <= u.minValue 且 u.maxValue <= r），并且，这个区间内所有数的奇偶性都和 c 一致（例如，c=1 且 u.evenCount == 0），那么太棒了！我们可以对整个节点进行一次性更新：
  - 这个区间有多少个数需要被减1？就是 u.oddCount (如果 c=1) 或 u.evenCount (如果 c=0)。我们把 totalSum 减去这个数量。
  - 给这个节点打上一个 -1 的懒标记（或者说，让 lazyValue 减 1）。
  - 因为所有数都减了1，奇偶性会翻转。所以我们交换 u.oddCount 和 u.evenCount。
  - u.minValue 和 u.maxValue 也都减 1。
- 部分命中 (需要深入): 如果以上情况都不满足，说明当前区间只有部分元素需要修改。这时候，我们就需要：
  - 先把当前节点的 lazyValue 下推给它的两个子节点，并清空自己的懒标记。
  - 递归地对左子节点和右子节点执行修改操作。
  - 当左右子节点的修改都完成后，用它们更新后的信息来更新当前节点的信息（pushup操作）。

懒标记的细节

pushdown 的时候要注意，当一个父节点的懒标记 delta 下推给子节点时：

子节点的 lazyValue 也要加上 delta。
子节点的 minValue 和 maxValue 也要加上 delta。
如果 delta 是一个奇数，那么子节点区间内所有数的奇偶性都会翻转，所以需要交换子节点的 oddCount 和 evenCount。

通过这套组合拳，我们就可以把每次操作的复杂度从 $O(n)$ 降低到 $O(\log n)$ 级别，整个问题就迎刃而解啦！

代码实现

这是我根据上面的思路，精心重构的一份代码，注释很详细的哦，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 为了方便，我们用 long long 来防止溢出
using ll = long long;

const int MAXN = 500005;

// 初始数组
int initial_a[MAXN];
// 全局总和
ll totalSum = 0;

// 线段树节点结构体
struct Node {
    int minValue, maxValue; // 区间内的最小值和最大值
    int oddCount, evenCount; // 奇数和偶数的数量
    int lazyValue; // 懒标记，记录区间整体被减了多少
};

Node tree[MAXN * 4];

// --- 线段树核心函数 ---

// pushup: 从子节点更新父节点信息
void pushup(int u) {
    tree[u].minValue = std::min(tree[u << 1].minValue, tree[u << 1 | 1].minValue);
    tree[u].maxValue = std::max(tree[u << 1].maxValue, tree[u << 1 | 1].maxValue);
    tree[u].oddCount = tree[u << 1].oddCount + tree[u << 1 | 1].oddCount;
    tree[u].evenCount = tree[u << 1].evenCount + tree[u << 1 | 1].evenCount;
}

// apply_lazy: 将懒标记应用到节点上
void apply_lazy(int u, int value) {
    if (value == 0) return; // 没有变化，直接返回
    tree[u].minValue += value;
    tree[u].maxValue += value;
    // 如果减去的值是奇数，奇偶性会翻转
    if (std::abs(value) % 2 == 1) {
        std::swap(tree[u].oddCount, tree[u].evenCount);
    }
    tree[u].lazyValue += value;
}

// pushdown: 将父节点的懒标记下推到子节点
void pushdown(int u) {
    if (tree[u].lazyValue != 0) {
        apply_lazy(u << 1, tree[u].lazyValue);
        apply_lazy(u << 1 | 1, tree[u].lazyValue);
        tree[u].lazyValue = 0; // 清空父节点懒标记
    }
}

// build: 构建线段树
void build(int u, int l, int r) {
    if (l == r) {
        tree[u].minValue = tree[u].maxValue = initial_a[l];
        if (initial_a[l] % 2 != 0) {
            tree[u].oddCount = 1;
            tree[u].evenCount = 0;
        } else {
            tree[u].oddCount = 0;
            tree[u].evenCount = 1;
        }
        tree[u].lazyValue = 0;
        return;
    }
    int mid = l + (r - l) / 2;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

// update: 在值域 [val_l, val_r] 上对特定奇偶性的数减1
void update(int u, int l, int r, int val_l, int val_r, int parity) {
    // 剪枝1: 当前节点的值域与查询值域无交集
    if (tree[u].maxValue < val_l || tree[u].minValue > val_r) {
        return;
    }
    
    // 剪枝2: 当前节点没有需要修改的奇偶性类型的数
    if ((parity == 1 && tree[u].oddCount == 0) || (parity == 0 && tree[u].evenCount == 0)) {
        return;
    }

    // 完全命中: 当前节点值域被查询值域完全覆盖，且只包含目标奇偶性的数
    if (val_l <= tree[u].minValue && tree[u].maxValue <= val_r) {
        if (parity == 1 && tree[u].evenCount == 0) { // 全是奇数
            totalSum -= tree[u].oddCount;
            apply_lazy(u, -1);
            return;
        }
        if (parity == 0 && tree[u].oddCount == 0) { // 全是偶数
            totalSum -= tree[u].evenCount;
            apply_lazy(u, -1);
            return;
        }
    }

    // 部分命中: 需要下推懒标记并递归处理
    pushdown(u);
    
    int mid = l + (r - l) / 2;
    update(u << 1, l, mid, val_l, val_r, parity);
    update(u << 1 | 1, mid + 1, r, val_l, val_r, parity);
    
    pushup(u);
}


int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, q;
    std::cin >> n >> q;

    for (int i = 1; i <= n; ++i) {
        std::cin >> initial_a[i];
        totalSum += initial_a[i];
    }

    // 关键一步：排序！
    std::sort(initial_a + 1, initial_a + n + 1);

    // 构建线段树
    build(1, 1, n);

    ll final_ans = 0;
    for (int i = 1; i <= q; ++i) {
        int l, r, c;
        std::cin >> l >> r >> c;
        update(1, 1, n, l, r, c);
        final_ans ^= (static_cast<ll>(i) * totalSum);
    }

    std::cout << final_ans << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N \log N + Q \log N)$
- 首先，我们需要 $O(N \log N)$ 的时间来对初始数组进行排序。
- 构建线段树的时间是 $O(N)$ 。
- 对于每一次查询，我们对线段树进行一次修改操作。由于线段树的深度是 $O(\log N)$ ，并且在大部分情况下，我们都能通过剪枝或完全命中来优化，所以单次操作的平均复杂度是 $O(\log N)$ 。在最坏情况下，一次更新可能会分裂成多个分支，但总体来看，每次查询访问的节点数是可控的。因此， $Q$ 次查询的总时间是 $O(Q \log N)$ 。
- 所以总的时间复杂度就是 $O(N \log N + Q \log N)$ ，完全可以通过本题的数据范围，喵~
空间复杂度: $O(N)$
- 我们需要一个数组来存储初始数据，空间为 $O(N)$ 。
- 线段树需要大约 $4N$ 的空间来存储节点，所以空间复杂度是 $O(N)$ 。

知识点总结

这道题真是一次有趣的冒险呢！我们来总结一下这次冒险中学到的武功秘籍吧：

问题转化: 当操作是基于值域而非下标时，一个非常强大的技巧是先对数组排序，然后将问题转化为在有序序列上的操作。
值域线段树: 本质上我们是建立了一个线段树来维护排序后数组的值。每个节点维护的 minValue 和 maxValue 实际上定义了该节点能处理的值的范围。
懒标记的灵活运用: 懒标记不只可以记录加减，还可以通过一些逻辑来处理更复杂的状态变化。在这里，我们通过判断懒标记的奇偶性来决定是否要翻转区间内元素的奇偶性计数，这是非常巧妙的一点。
多重剪枝: 在线段树的递归过程中，有效的剪枝是性能的关键。本题中，我们同时利用了值域范围和奇偶性数量两个维度进行剪枝，大大提高了效率。

希望这篇题解能让你对线段树有更深的理解！继续加油哦，指挥官，我会一直为你应援的，喵~！

数据结构 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键的转化：从操作索引到操作值 ​

线段树的设计 ​

操作流程详解 ​

懒标记的细节 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​