D. Xenia and Bit Operations - 题解

比赛与标签

比赛: Codeforces Round 197 (Div. 2) 标签: data structures, trees 难度: *1700

题目大意喵~

早上好，各位算法大师们，喵~！今天我们要解决的是一道关于位运算的有趣问题呐。

题目给了我们一个长度为 2^n 的整数序列 a。可爱的 Xenia 会对这个序列进行 n 轮操作，直到最后只剩下一个数字 v。 操作规则是这样的：

• 第一轮: 将序列中相邻的两个数进行 按位或(OR) 运算，得到一个长度为 2^(n-1) 的新序列。
• 第二轮: 将新序列中相邻的两个数进行 按位异或(XOR) 运算，得到一个长度为 2^(n-2) 的新序列。
• 第三轮: 再次进行 按位或(OR) 运算...
• ...以此类推，OR 和 XOR 操作交替进行，直到最后只剩下一个数。

举个例子，如果 a = (1, 2, 3, 4)，那么 n=2。

1. 第一轮 (OR): (1 or 2, 3 or 4) -> (3, 7)
2. 第二轮 (XOR): (3 xor 7) -> (4) 所以最终得到的 v 就是 4 啦！

我们的任务不是一次性算出 v 就好，而是要处理 m 个查询。每个查询会把序列中某个位置 p 的值修改为 b，然后我们都需要快速计算出修改后新的 v 是多少，并把它打印出来。

解题思路喵~

每次修改一个数就要重新算一遍，如果每次都从头模拟一遍，那也太慢了，肯定会超时的说！( TωT ) 我们需要一个更聪明的办法。

仔细观察这个计算过程，是不是很像一棵树的结构呢？

• 最底层的 2^n 个数字就是树的 叶子节点。
• 每两个相邻的叶子节点通过 OR 运算合并，生成了它们的父节点。
• 这些父节点再两两相邻，通过 XOR 运算合并，生成了它们的爷爷节点...
• 这样一层一层往上合并，直到最顶端的 根节点，这个根节点的值就是我们最终想要的 v 啦！

这不就是传说中的 线段树（Segment Tree） 嘛！喵~ 线段树最擅长的就是处理区间信息和单点更新了，完美契合我们的需求！

接下来就是如何构建这棵特殊的线段树了。 普通线段树的每一层节点做的操作都是一样的（比如求和、求最大值），但我们这里的操作是 OR 和 XOR 交替的。这该怎么办呢？

别担心，我们只需要在构建和更新树的时候，记录一下当前节点在第几层，然后根据层数的奇偶性来决定是做 OR 还是 XOR 操作就好了！

一个更简单的实现方法是，我们从根节点开始递归建树，并传递一个标志位 is_or。

1. 判断根节点的操作：整个过程有 n 轮合并。第一轮是 OR，第二轮是 XOR... 那么第 k 轮操作，如果 k 是奇数就是 OR，偶数就是 XOR。我们的根节点是第 n 轮合并的结果，所以：
   • 如果 n 是 奇数，根节点的操作就是 OR。
   • 如果 n 是 偶数，根节点的操作就是 XOR。
2. 递归建树：
   • 我们从根节点开始，带着这个初始的标志位 is_or 向下递归。
   • 当我们从父节点递归到子节点时，层数变了，操作也应该反转。所以，我们只需要把标志位取反 (!is_or) 再传给子节点就好啦！
   • 递归到叶子节点时，直接读入初始数组的值。
   • 回溯时，根据当前层的标志位 is_or，用对应的位运算（OR 或 XOR）合并左右子节点的值，更新当前父节点。

更新操作 也是一样的道理： 当我们要把 a[p] 修改为 b 时，这相当于更新了线段树的一个叶子节点。我们从根节点出发，找到对应的叶子节点并修改它的值。然后沿着路径一路返回到根节点，在回溯的路上，依次更新所有父节点的值。因为每个节点的运算类型是固定的，所以更新过程和建树过程的逻辑是一样的！

这样一来，每次更新操作只需要修改从叶子到根的一条路径上的节点，时间复杂度就是树的高度，也就是 O(log(2^n)) = O(n)。对于 m 次查询，总时间复杂度就是 O(m * n)，加上建树的 O(2^n)，完全可以接受！

每次查询的答案，就是我们线段树根节点 tree[1] 的值，直接输出就好啦，是不是很优雅呢？喵~

代码实现喵~

#include <iostream>
#include <vector>
#include <cmath>

// 全局变量，方便函数调用喵~
int n_val, m_val;
int N; // 代表 2^n
std::vector<int> tree;

// build函数，用来构建我们的神奇线段树~
// node: 当前节点在tree数组中的索引 (1-based)
// start, end: 当前节点代表的原始数组区间 (1-based)
// is_or: 一个布尔标志，true代表这层用OR，false代表用XOR
void build(int node, int start, int end, bool is_or) {
    if (start == end) {
        // 到达叶子节点啦，这里对应着初始数组的一个元素
        std::cin >> tree[node];
        return;
    }

    int mid = start + (end - start) / 2;
    // 递归去构建左子树和右子树
    // 注意！传给下一层的操作是当前层的反操作哦，所以是 !is_or
    build(2 * node, start, mid, !is_or);
    build(2 * node + 1, mid + 1, end, !is_or);

    // 从子节点回溯后，根据当前层的操作，合并左右子树的结果
    if (is_or) {
        tree[node] = tree[2 * node] | tree[2 * node + 1];
    } else {
        tree[node] = tree[2 * node] ^ tree[2 * node + 1];
    }
}

// update函数，用于修改某个值并更新整棵树
// node, start, end, is_or: 和build函数里的一样
// idx: 要更新的原始数组的索引 (1-based)
// val: 要更新成的新值
void update(int node, int start, int end, int idx, int val, bool is_or) {
    if (start == end) {
        // 找到要更新的叶子节点了，把它的值改掉
        tree[node] = val;
        return;
    }

    int mid = start + (end - start) / 2;
    if (idx <= mid) {
        // 要更新的索引在左子树的范围里
        update(2 * node, start, mid, idx, val, !is_or);
    } else {
        // 在右子树的范围里
        update(2 * node + 1, mid + 1, end, idx, val, !is_or);
    }

    // 更新完子节点后，也要重新计算当前节点的值，逻辑和build时一样
    if (is_or) {
        tree[node] = tree[2 * node] | tree[2 * node + 1];
    } else {
        tree[node] = tree[2 * node] ^ tree[2 * node + 1];
    }
}

int main() {
    // 加速一下输入输出，跑得更快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n_val >> m_val;
    N = 1 << n_val; // 用位运算计算 2^n，又快又酷

    // 线段树一般需要4倍原始数组大小的空间才保险
    tree.resize(4 * N);

    // 决定根节点的操作类型
    // 总共有 n 轮合并。
    // 第1轮是OR, 第2轮是XOR, 第3轮是OR...
    // 所以第n轮（也就是根节点这层）的操作，在n为奇数时是OR，偶数时是XOR。
    bool root_is_or = (n_val % 2 == 1);
    
    // 从输入数据开始，构建初始的线段树
    build(1, 1, N, root_is_or);

    // 处理 m 次查询
    for (int i = 0; i < m_val; ++i) {
        int p, b;
        std::cin >> p >> b;
        // 在p位置更新值为b
        update(1, 1, N, p, b, root_is_or);
        // 树的根节点 tree[1] 永远保存着最终的计算结果v
        std::cout << tree[1] << "\n";
    }

    return 0;
}

复杂度分析喵~

• 时间复杂度: O(2^n + m*n) 的说。

  • 建树 build 需要访问线段树的每一个节点，节点总数大约是 2 * 2^n 的两倍，所以是 O(2^n)。
  • 每次 update 操作，我们只更新从叶子到根的一条路径，树的高度是 log(2^n) = n。所以单次更新是 O(n)。进行 m 次更新，就是 O(m*n)。
  • 总和起来就是 O(2^n + m*n)，完全可以跑过！

• 空间复杂度: O(2^n) 的说。

  • 我们需要一个数组来存储线段树，对于 N = 2^n 个叶子，数组大小通常开到 4*N 来防止越界。所以空间复杂度是 O(4 * 2^n)，也就是 O(2^n)。

知识点与总结喵~

这道题真是太棒了，把位运算和数据结构巧妙地结合在了一起呢！

1. 核心数据结构: 线段树。当遇到对一个序列进行频繁的单点修改和区间/全局查询时，一定要先想想线段树能不能解决！
2. 问题转化能力: 解题的关键在于，要能看出题目中描述的层层递进的运算过程，本质上是一个树形结构。把这个过程抽象成线段树模型，问题就解决了一大半啦。
3. 灵活的递归: 通过在递归函数中传递一个额外的状态（这里的 is_or 标志），我们可以让线段树的每一层执行不同的操作。这是一个非常实用的技巧，大家要记住哦！
4. 位运算: 当然啦，对 OR (|) 和 XOR (^) 的理解是基础中的基础。

总之，这是一道非常经典的线段树变种题。只要抓住了问题核心的树形结构，再用一点点小技巧处理交替操作，就能轻松AC啦！希望这篇题解能帮到你，加油哦，你一定可以的！喵~ (ฅ'ω'ฅ)