F. Hossam and Range Minimum Query - 题解

比赛与标签

比赛: Codeforces Round 837 (Div. 2) 标签: binary search, bitmasks, data structures, hashing, probabilities, strings, trees 难度: *2500

题目大意喵~

主人你好呀~！这道题是说，我们有一个长度为 n 的整数序列 a，然后会有 q 次询问，喵~

对于每一次询问，我们会得到一个区间 [l, r]。我们的任务是，在这个子序列 a[l], a[l+1], ..., a[r] 中，找到出现次数为 奇数 的 最小 的那个数。如果不存在这样的数，就输出 0。

还有一个小小的挑战哦！这个题目的查询是 强制在线 的。也就是说，第 i 次查询的 l 和 r 是由第 i-1 次查询的答案 ans 计算得出的（l = a' ^ ans, r = b' ^ ans）。所以我们必须处理完一个查询才能知道下一个查询的具体范围，不能把所有查询都读进来再一起处理啦，喵~

解题思路大揭秘！

这道题要求在线查询区间内出现奇数次的最小数，n 和 q 的范围都是 2 * 10^5，一个朴素的 O(n*q) 暴力解法肯定是会超时的说。看到 "区间查询" 和 "在线"，我们就应该往高效的数据结构方向去想啦，比如线段树或者树状数组。

步骤一：如何判断“奇数次”？

一看到“奇数次”、“偶数次”，我们聪明的猫娘脑海里就应该立刻闪过一个神奇的运算符——异或（XOR），喵！

异或有一个超棒的性质：x ^ x = 0，并且 x ^ 0 = x。 这意味着，如果一个数字出现偶数次，它自己和自己异或偶数次后就会变成 0，完全消失了！如果它出现奇数次，最后就会留下它自己。

但是，如果我们直接对区间内所有数字做异或和，比如 1, 2, 1, 3，异或和是 1^2^1^3 = 2^3 = 1。这个结果并不能直接告诉我们是哪个数出现了奇数次。

步骤二：给数字一个“身份证”——哈希！

为了解决上面的问题，我们可以不直接对数字本身做异或，而是给每个不同的数字一个独一无二的、随机的64位哈希值（就像是它们的身份证号码！）。

我们对区间内所有数字的 哈希值 进行异或。

• 如果一个数字出现偶数次，它的哈希值也被异或了偶数次，结果为 0。
• 如果一个数字出现奇数次，它的哈希值就被异或了奇数次，最终会保留下来。

这样，如果一个区间的哈希异或和为 0，我们就可以（以极高的概率）认为这个区间里所有数都出现了偶数次。如果不为 0，就说明至少有一个数出现了奇数次。

步骤三：处理区间查询——前缀异或和！

要快速计算区间 [l, r] 的哈希异或和，我们可以使用前缀和的思想。设 prefix_hash[i] 是 a[1...i] 中所有元素哈希值的异或和。

那么，区间 [l, r] 的哈希异或和就是 prefix_hash[r] ^ prefix_hash[l-1]。这样我们就可以 O(1) 地得到一个区间的总哈希异或和了！

步骤四：找到“最小”的那个数——主席树登场！

现在我们能判断区间内是否存在出现奇数次的数，但还不知道哪个是最小的。我们需要一个更强大的数据结构，它不仅能维护前缀哈希和，还能支持我们查找。

这就是 可持久化线段树（主席树） 的用武之地啦，喵~

1. 离散化：因为 a_i 的值域很大（高达 10^9），但数量 n 不算太大，我们先把所有 a_i 离散化，将它们映射到 [1, m] 的排名上（m 是不同数值的个数）。
2. 建树：我们建立一棵基于 排名 的线段树。roots[i] 保存的是序列前缀 a[1...i] 对应的线段树的根节点。这棵树的每个节点 node 存储一个 hash_val，表示在 a[1...i] 中，所有排名落在 node 所代表的排名区间的数字的哈希异或和。
3. 可持久化：roots[i] 的树是从 roots[i-1] 的树上“长”出来的。处理 a[i] 时，我们只需要在 roots[i-1] 的树上，更新 a[i] 对应排名的那条路径上的哈希值（异或上 a[i] 的哈希值），其他节点直接复用 roots[i-1] 的，这样既省时又省空间，喵~
4. 查询：对于查询 [l, r]，我们拿出 roots[r] 和 roots[l-1] 这两棵树。
   • 首先，比较根节点的哈希值。如果 tree[roots[r]].hash_val == tree[roots[l-1]].hash_val，说明区间 [l, r] 的总哈希异或和为 0，没有奇数次出现的数，答案是 0。
   • 如果不相等，说明有！为了找到最小的那个，我们可以在这两棵树上同时进行类似二分查找的操作：
     • 比较它们左子树的哈希值。如果 tree[left_r].hash_val != tree[left_{l-1}].hash_val，说明左子树代表的排名区间里，一定有出现奇数次的数。因为我们要找最小的，所以我们往左子树走。
     • 如果左子树的哈希值相等，说明奇数次出现的数一定在右子树代表的排名区间里，我们就往右子树走。
   • 我们这样一直走到叶子节点，这个叶子节点对应的排名就是出现奇数次的数中排名最小的那个。最后再把这个排名转换回原来的数值，就得到答案啦！

总结一下就是：离散化 + 哈希 + 主席树，完美解决！呐，是不是很巧妙呢？

代码实现喵~

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

// 使用一个高质量的随机数生成器来创建哈希值，喵~
// mt19937_64 速度快，随机性也好，非常适合做哈希！
struct custom_rng {
    std::mt19937_64 rng;
    custom_rng() : rng(std::chrono::steady_clock::now().time_since_epoch().count()) {}
    uint64_t operator()() {
        return rng();
    }
};
custom_rng rnd;

const int MAXN = 200005;
const int MAX_NODES = MAXN * 22; // 主席树节点空间，n*logm 级别，开大一点保险

struct Node {
    int l_child, r_child; // 左右子节点的编号
    uint64_t hash_val;    // 节点所代表区间的哈希异或和
};

Node tree[MAX_NODES];
int node_count = 0; // 当前使用的节点数
int roots[MAXN];    // roots[i] 存储前缀 a[1...i] 对应的主席树根节点

int n, m; // n: 数组大小, m: 不同值的数量
std::vector<int> a;
std::vector<int> unique_vals; // 存储离散化后的唯一值
std::vector<uint64_t> hashes; // 存储每个唯一值的哈希值

// 构建一棵空的线段树，哈希值都为0
int build(int l, int r) {
    int curr = ++node_count;
    tree[curr].hash_val = 0;
    if (l == r) {
        tree[curr].l_child = tree[curr].r_child = 0;
        return curr;
    }
    int mid = l + (r - l) / 2;
    tree[curr].l_child = build(l, mid);
    tree[curr].r_child = build(mid + 1, r);
    return curr;
}

// 主席树的更新操作
// prev 是上一个版本的根，pos 是要更新的排名，h_val 是对应排名的哈希值
int update(int prev, int l, int r, int pos, uint64_t h_val) {
    int curr = ++node_count; // 创建一个新节点
    tree[curr] = tree[prev]; // 复制上一个版本的信息
    tree[curr].hash_val ^= h_val; // 更新当前节点的哈希值

    if (l == r) {
        return curr; // 到达叶子节点，返回
    }

    int mid = l + (r - l) / 2;
    if (pos <= mid) {
        // 如果更新位置在左子树，递归更新左子树，右子树保持不变
        tree[curr].l_child = update(tree[prev].l_child, l, mid, pos, h_val);
    } else {
        // 否则递归更新右子树，左子树保持不变
        tree[curr].r_child = update(tree[prev].r_child, mid + 1, r, pos, h_val);
    }
    return curr;
}

// 在主席树上查找出现奇数次的最小数
// u 是 r 版本的根，v 是 l-1 版本的根
int find_smallest(int u, int v, int l, int r) {
    if (l == r) {
        // 找到叶子节点了，它对应的排名就是答案
        return l;
    }
    
    int mid = l + (r - l) / 2;
    // 比较左右子树的哈希值，判断奇数次出现的数在哪一半
    if (tree[tree[u].l_child].hash_val != tree[tree[v].l_child].hash_val) {
        // 左子树的哈希值不同，说明答案在左半边，往左走
        return find_smallest(tree[u].l_child, tree[v].l_child, l, mid);
    } else {
        // 否则答案在右半边，往右走
        return find_smallest(tree[u].r_child, tree[v].r_child, mid + 1, r);
    }
}

void solve() {
    std::cin >> n;
    a.resize(n);
    std::vector<int> temp_vals(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        temp_vals[i] = a[i];
    }

    // 离散化
    std::sort(temp_vals.begin(), temp_vals.end());
    temp_vals.erase(std::unique(temp_vals.begin(), temp_vals.end()), temp_vals.end());
    unique_vals = temp_vals;
    m = unique_vals.size();

    // 如果数组为空，所有查询都返回0
    if (m == 0) {
        int q;
        std::cin >> q;
        for (int i = 0; i < q; ++i) {
            int l_in, r_in;
            std::cin >> l_in >> r_in;
            std::cout << 0 << "\n";
        }
        return;
    }

    // 为每个唯一的数值生成一个随机哈希值
    hashes.resize(m + 1);
    for (int i = 1; i <= m; ++i) {
        hashes[i] = rnd();
    }

    // roots[0] 是一棵空树
    roots[0] = build(1, m);
    // 构建 1 到 n 的所有前缀版本的主席树
    for (int i = 0; i < n; ++i) {
        // 找到 a[i] 对应的排名 (1-based)
        int rank = std::lower_bound(unique_vals.begin(), unique_vals.end(), a[i]) - unique_vals.begin() + 1;
        // 在上一个版本的基础上，更新 a[i] 对应排名的哈希值
        roots[i + 1] = update(roots[i], 1, m, rank, hashes[rank]);
    }

    int q;
    std::cin >> q;
    long long last_ans = 0;
    for (int i = 0; i < q; ++i) {
        int l_in, r_in;
        std::cin >> l_in >> r_in;
        // 解码出真实的 l 和 r
        int l = (int)(l_in ^ last_ans);
        int r = (int)(r_in ^ last_ans);

        int root_r = roots[r];
        int root_l_minus_1 = roots[l - 1];

        // 比较 r 和 l-1 版本根节点的哈希值
        if (tree[root_r].hash_val == tree[root_l_minus_1].hash_val) {
            // 如果相等，说明区间内所有数都出现偶数次
            last_ans = 0;
        } else {
            // 否则，在树上查找最小的那个
            int rank_ans = find_smallest(root_r, root_l_minus_1, 1, m);
            // 将排名转换回原始值
            last_ans = unique_vals[rank_ans - 1];
        }
        std::cout << last_ans << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}

复杂度分析的说

• 时间复杂度: O((n+q) log m) 的说。

  • 离散化: 对 n 个数排序去重，需要 O(n log n)。
  • 建树: 我们要对 n 个元素进行 n 次更新，每次更新主席树会创建 O(log m) 个新节点（m 是唯一值的数量），所以建树总时间是 O(n log m)。
  • 查询: 我们有 q 次查询，每次查询在主席树上遍历的深度是 O(log m)，所以查询总时间是 O(q log m)。
  • 因为 m <= n，所以总的时间复杂度可以看作是 O((n+q) log n)，对于这道题的数据范围来说是完全可以接受的，喵~

• 空间复杂度: O(n log m) 的说。

  • 主席树的空间开销是主要部分。每次更新都会创建 O(log m) 个新节点。n 次更新就会创建 O(n log m) 个节点。所以空间复杂度就是 O(n log m)。

知识点与总结

这道题真是一道非常经典的数据结构好题呢，融合了多种算法思想，做完之后收获满满！

1. 核心数据结构: 可持久化线段树（主席树） 是解决这道题的关键。它能高效地维护序列的历史版本，从而让我们能方便地查询任意区间的状态。

2. 核心思想:

   • 哈希 + 异或: 这是处理“出现奇偶次”问题的经典组合技。用随机哈希来给每个元素一个唯一的标识，再用异或的性质来消除出现偶数次的元素。
   • 前缀思想: 将区间问题转化为两个前缀的差（在这里是异或），是解决各类区间问题的通用技巧。主席树就是前缀思想在树形结构上的完美体现。
   • 树上二分: 在主席树上通过比较左右子树的哈希值来决定搜索方向，本质上是在排好序的唯一值集合上进行二分查找，从而找到满足条件的最小值。

3. 编程技巧与注意事项:

   • 强制在线: 一定要注意题目要求，这决定了我们不能使用莫队等离线算法。
   • 离散化: 当数值范围很大但元素数量有限时，离散化是必须的预处理步骤。
   • 哈希随机性: 为了防止被构造数据卡掉，使用基于时间的 mt19937_64 来生成随机哈希值是一个好习惯，比简单的 rand() 要可靠得多。

希望这篇题解能帮助到你哦！继续加油，算法的世界还有更多有趣的东西等着我们去探索，喵~ >w<