Interval - 题解

标签与难度

标签: 数据结构, 主席树, 位运算, 离线思想, 动态规划难度: 2400

题目大意喵~

主人你好呀~！这道题是这样的喵：

我们有一个长度为 $N$ 的数列 $A$ 。首先定义一个函数 $F(l, r)$ ，它表示数列 $A$ 从下标 $l$ 到 $r$ 的所有元素的按位与（Bitwise AND）结果，也就是 $A_l \& A_{l+1} \& \dots \& A_r$ 。

然后，对于一个区间 $[L, R]$ ，我们定义一个集合 $S(L, R)$ 。这个集合包含了所有在 $[L, R]$ 范围内的子区间 $[a, b]$ （即 $L \le a \le b \le R$ ）所能产生的 $F(a, b)$ 的不同值。

接下来有 $Q$ 次查询。每次查询会给你两个数 $L'$ 和 $R'$ ，但真正的查询区间 $[L, R]$ 需要通过上一次查询的答案 lastans 来计算（初始 lastans 为 0）：

$L = (L' \oplus \text{lastans}) \% N + 1$
$R = (R' \oplus \text{lastans}) \% N + 1$ （这里的 $\oplus$ 是按位异或 XOR 的意思哦）

如果计算出的 $L > R$ ，就需要交换它们。你的任务就是，对于每一次查询，告诉本喵集合 $S(L, R)$ 的大小是多少，也就是在查询区间 $[L, R]$ 内的所有子区间能产生多少种不同的按位与结果，喵~

因为每次查询都依赖上一次的答案，所以我们必须在线处理，不能把所有查询读完再一起处理呢。

解题思路分析

这道题看起来有点吓人，要在一个区间里找所有子区间的 AND 值，还要去重计数，而且还是强制在线的，呜... 但是别怕，让我带你一步步拆解它，喵~

核心问题的转化

我们的目标是求 $|S(L, R)| = |\{ F(a, b) \mid L \le a \le b \le R \}|$ 。

直接处理这个二维区间 $(a, b)$ 的问题非常困难。我们不妨换个角度思考。对于一个数值 v，它什么时候会被计入答案呢？当且仅当存在一个子区间 $[a, b]$ ，满足 $L \le a \le b \le R$ 且 $F(a, b) = v$ 。

为了不重复计数，我们通常会给每个值 v 找一个“代言人”，只数这些“代言人”。一个好方法是，对于每个能被计算出的值 v，我们只关心它最晚是在哪里出现的。

我们定义一个 latest_start_pos(v, R)，表示对于所有右端点不超过 $R$ 的、能产生值 v 的子区间 $[p, q]$ （即 $F(p, q) = v$ 且 $q \le R$ ）中，那个起始位置 $p$ 的最大值。

现在，本喵有一个关键的结论，喵！

结论： 一个值 v 会在查询 (L, R) 中被计入答案，当且仅当 latest_start_pos(v, R) >= L。

证明一下喵~

充分性 (<=): 如果 latest_start_pos(v, R) = p >= L，根据定义，存在一个子区间 $[p, q]$ 使得 $F(p, q) = v$ 并且 $q \le R$ 。因为 $p$ 是起始位置，所以必然有 $p \le q$ 。这样我们就找到了一个子区间 $[p, q]$ ，它满足 $L \le p \le q \le R$ ，完美地落在了查询范围内。所以 v 应该被计入答案。
必要性 (=>): 如果 v 应该被计入答案，那么必定存在一个子区间 $[a, b]$ 满足 $L \le a \le b \le R$ 且 $F(a, b) = v$ 。根据 latest_start_pos 的定义，latest_start_pos(v, R) 是所有满足条件的起始位置中最大的一个，所以 latest_start_pos(v, R) >= a。又因为 $a \ge L$ ，所以 latest_start_pos(v, R) >= L。

证毕！这下问题就转化为：对于给定的查询 $(L, R)$ ，我们需要计算满足 latest_start_pos(v, R) >= L 的不同值 v 的数量。

动态处理与主席树

这个问题还是和 $R$ 有关。由于查询是强制在线的，我们不能离线处理。一个自然的想法是，当我们从右端点 $i-1$ 移动到 $i$ 时，我们来更新所有值的 latest_start_pos。这种“历史版本”查询的问题，正是主席树（Persistent Segment Tree） 的拿手好戏，喵！

我们可以建立 $N$ 棵线段树，第 $R$ 棵线段树 root[R] 记录了当右端点最大考虑到 $R$ 时的信息。具体来说，root[R] 这棵树是一棵权值线段树（其实是下标线段树），它的区间是 [1, N]。树上位置 p 的值表示：是否存在某个值 v，使得 latest_start_pos(v, R) = p。如果存在，我们就让这个位置为1，否则为0。

这样，对于查询 (L, R)，我们只需要在第 $R$ 棵主席树上查询区间 [L, N] 的和，就能得到答案了！

如何高效更新？

现在最大的挑战就是，如何从 root[R-1] 高效地构建出 root[R] 呢？

首先，latest_start_pos(v, R) 的更新规则是：

\text{latest\_start\_pos}(v, R) = \max(\text{latest\_start\_pos}(v, R-1), \max\{p \mid F(p, R) = v\})

这意味着，在处理 $A_R$ 时，我们只关心那些新产生的、或者因为 $A_R$ 的加入而获得了更晚起始位置的值。这些都是由右端点为 $R$ 的子区间 [p, R] 产生的。

一个非常重要的性质来了，快拿出小本本记下，喵~ 性质： 对于固定的右端点 $R$ ，当左端点 $p$ 从 $R$ 向 $1$ 递减时，F(p, R) 的值是非递增的（F(p-1, R) = F(p, R) & A_{p-1} <= F(p, R)）。因为数值的位数有限（比如32位），所以 $F(p, R)$ 的值最多只会变化 $30$ 次左右！

这意味着，在所有以 $R$ 结尾的子区间中，只会产生 $O(\log(\max A))$ 个不同的按位与值。好耶！

我们可以用一个 map 或者 unordered_map，叫做 current_values，来记录以 $R$ 结尾能产生的所有不同值和它们对应的最大起始位置。 current_values[v] = p 表示 $F(p, R) = v$ 且 $p$ 是最大的。

我们可以通过动态规划的思想来计算 current_values。假设我们已经知道了以 $R-1$ 结尾的所有值和它们的最大起始位置，存在 prev_values 里。那么对于 current_values：

对于 prev_values 中的每一个 (v, p) 对，我们都可以延伸它得到一个新的子区间 [p, R]，它的值是 v & A[R]。所以我们更新 current_values[v & A[R]] = max(current_values[v & A[R]], p)。
别忘了还有新的子区间 [R, R]，它的值是 $A_R$ ，起始位置是 $R$ 。所以 current_values[A[R]] = max(current_values[A[R]], R)。

这样我们就得到了所有以 $R$ 结尾的 (值, 最大起始位置) 对。

然后，我们用 current_values 来更新全局的 latest_start_pos 信息，并同步更新主席树。我们用一个全局的 map 叫 global_latest_pos 来存储 latest_start_pos(v, R)。

For each (v, p) in current_values:

设 old_p = global_latest_pos[v]（如果不存在则为0）。
如果 p > old_p，说明我们为 v 找到了一个更晚的起始位置！
- 我们需要在主席树上进行两次更新：在 old_p 的位置 -1（如果 old_p > 0），在 p 的位置 +1。
- 同时更新 global_latest_pos[v] = p。

这整个过程，从 root[R-1] 到 root[R]，只会涉及 $O(\log A)$ 次主席树的更新。每次更新的复杂度是 $O(\log N)$ 。

总的流程就是：

初始化，root[0] 是一棵空树。
循环 $i$ 从 $1$ 到 $N$ ： a. root[i] 先继承 root[i-1]。 b. 计算出以 $i$ 结尾的所有 (值, 最大起始位置) 对，存入 values_ending_at_i。 c. 遍历 values_ending_at_i 中的每一对 (v, p)。 d. 更新全局的 global_latest_pos[v]，并在主席树上做相应的 +1 和 -1 操作，得到最终的 root[i]。
对于每个查询 (L, R)，在 root[R] 上查询区间 [L, N] 的和即可。

这样，我们就能愉快地解决这道题啦，喵~

代码实现

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

cpp

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

// 为了让代码更清晰，定义一些别名，喵~
using ll = long long;

const int MAXN = 100005;
const int MAX_NODES = MAXN * 35 * 2; // N * logA * logN -> 1e5 * 32 * 2 (updates) is safer

// 主席树的节点
struct Node {
    int left_child = 0, right_child = 0;
    int count = 0;
};

Node tree[MAX_NODES];
int root[MAXN];
int node_count = 0;
int n;

// 创建一个新节点
int create_node(int old_node) {
    node_count++;
    tree[node_count] = tree[old_node];
    return node_count;
}

// 主席树的单点更新
// 在版本 prev_version 的基础上，将 pos 位置的值增加 val
int update(int prev_version, int pos, int val, int l, int r) {
    int current_version = create_node(prev_version);
    tree[current_version].count += val;
    
    if (l == r) {
        return current_version;
    }
    
    int mid = l + (r - l) / 2;
    if (pos <= mid) {
        tree[current_version].left_child = update(tree[prev_version].left_child, pos, val, l, mid);
    } else {
        tree[current_version].right_child = update(tree[prev_version].right_child, pos, val, mid + 1, r);
    }
    return current_version;
}

// 主席树的区间查询
// 在版本 version 上查询区间 [query_l, query_r] 的和
int query(int version, int query_l, int query_r, int l, int r) {
    if (!version || query_l > r || query_r < l) {
        return 0;
    }
    if (query_l <= l && r <= query_r) {
        return tree[version].count;
    }
    
    int mid = l + (r - l) / 2;
    int result = 0;
    result += query(tree[version].left_child, query_l, query_r, l, mid);
    result += query(tree[version].right_child, query_l, query_r, mid + 1, r);
    return result;
}

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

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

    // `global_latest_pos[v]` 存储值 v 出现过的最大起始位置
    std::unordered_map<int, int> global_latest_pos;
    // `values_ending_at_prev_i` 存储以 i-1 结尾的 (值, 最大起始位置) 对
    std::unordered_map<int, int> values_ending_at_prev_i;

    // 预处理，构建N棵主席树
    root[0] = 0;
    for (int i = 1; i <= n; ++i) {
        // 当前版本继承自上一个版本
        root[i] = root[i - 1];
        
        // `values_ending_at_i` 存储以 i 结尾的 (值, 最大起始位置) 对
        std::unordered_map<int, int> values_ending_at_i;
        
        // 1. 从以 i-1 结尾的子区间延伸而来
        for (auto const& [val, pos] : values_ending_at_prev_i) {
            int new_val = val & a[i];
            // 如果新值已存在，取起始位置更大的那个
            if (values_ending_at_i.find(new_val) == values_ending_at_i.end() || pos > values_ending_at_i[new_val]) {
                 values_ending_at_i[new_val] = pos;
            }
        }
        
        // 2. 新的子区间 [i, i]
        if (values_ending_at_i.find(a[i]) == values_ending_at_i.end() || i > values_ending_at_i[a[i]]) {
            values_ending_at_i[a[i]] = i;
        }

        // 更新主席树
        for (auto const& [val, pos] : values_ending_at_i) {
            int old_pos = 0;
            if (global_latest_pos.count(val)) {
                old_pos = global_latest_pos[val];
            }
            
            if (pos > old_pos) {
                if (old_pos > 0) {
                    // 旧的起始位置不再是最大的了，把它从主席树里减掉
                    root[i] = update(root[i], old_pos, -1, 1, n);
                }
                // 新的最大起始位置，加到主席树里
                root[i] = update(root[i], pos, 1, 1, n);
                global_latest_pos[val] = pos;
            }
        }
        
        // 为下一次迭代做准备
        values_ending_at_prev_i = values_ending_at_i;
    }

    int q;
    std::cin >> q;
    int last_ans = 0;
    while (q--) {
        int l_prime, r_prime;
        std::cin >> l_prime >> r_prime;
        
        int l = (l_prime ^ last_ans) % n + 1;
        int r = (r_prime ^ last_ans) % n + 1;
        
        if (l > r) {
            std::swap(l, r);
        }
        
        // 在第 r 棵主席树上查询 [l, n] 区间有多少个“最大起始位置”
        last_ans = query(root[r], l, n, 1, n);
        std::cout << last_ans << "\n";
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N \cdot \log(\max A) \cdot \log N + Q \cdot \log N)$
- 预处理: 我们需要遍历数组中的 $N$ 个元素。对于每个元素 $A_i$ ，我们需要计算以 $i$ 结尾的子区间产生的不同 AND 值。我们已经知道这个数量是 $O(\log(\max A))$ 。对于每个这样的值，我们要在主席树上做一次或两次更新，每次更新的代价是 $O(\log N)$ 。所以预处理的总时间是 $O(N \cdot \log(\max A) \cdot \log N)$ 。
- 查询: 每次查询只需要在对应版本的主席树上进行一次区间查询，时间复杂度是 $O(\log N)$ 。总查询时间是 $O(Q \cdot \log N)$ 。
空间复杂度: $O(N \cdot \log(\max A) \cdot \log N)$
- 主席树在每次更新时会创建 $O(\log N)$ 个新节点。在预处理过程中，我们有 $N$ 个版本，每个版本会进行 $O(\log(\max A))$ 次更新。所以总的节点数是 $O(N \cdot \log(\max A) \cdot \log N)$ 。
- 此外，unordered_map 也会占用一些空间，但它的规模不会超过主席树。

知识点总结

这真是一道融合了多种思想的绝妙好题呢，喵！

问题转化: 把一个复杂的二维区间计数问题，通过定义 latest_start_pos 转化为一维的、带版本历史的计数问题。这是解题最关键的一步！
位运算性质: 巧妙地利用了按位与 & 操作的非递增性，将每次更新需要考虑的值的数量从 $O(N)$ 降低到了 $O(\log A)$ ，这是性能的保证。
主席树 (Persistent Segment Tree): 解决强制在线、查询历史版本问题的强大数据结构。在这里，它完美地存储了每个右端点 $R$ 对应的 latest_start_pos 的分布情况。
动态规划思想: 在从 $i-1$ 递推到 $i$ 的过程中，我们利用了上一步计算出的结果（以 $i-1$ 结尾的所有值）来高效计算当前步的结果，这其中蕴含了DP的思想。

希望我的讲解能帮助你彻底理解这道题，如果还有不懂的地方，随时可以再来问我哦，喵~

Interval - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

核心问题的转化 ​

动态处理与主席树 ​

如何高效更新？ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​