E. Distance Learning Courses in MAC 详解

题目理解

有 $n$ 门课程，第 $i$ 门课程的成绩可以是 $[x_i, y_i]$ 中的任意整数。
对于每个查询 $[l, r]$，你需要从每门课程中独立选择一个成绩 $c_i \in [x_i, y_i]$，使得：

$$\text{ans} = c_l \;|\; c_{l+1} \;|\; \dots \;|\; c_r $$

最大化，并输出这个最大值。

核心难点

• 每门课程的成绩可以在一个区间内选择，不是固定值。
• 按位或的性质：我们希望尽可能多的高位为 1。
• 直接贪心从高位到低位决策，但需要判断某一位是否能在区间内被置为 1。

关键观察

1. 区间化简

对于一门课程 $[x, y]$，考虑二进制表示。设 $p$ 为 $x$ 和 $y$ 最高的不同位（即 $x \oplus y$ 的最高位），那么：

• 高于 $p$ 的位，$x$ 和 $y$ 相同，这些位是固定的。
• 在 $p$ 位上，$x$ 为 0，$y$ 为 1。
• 低于 $p$ 的位，我们可以任意选择（通过选择合适的中值）。

实际上，我们可以将区间 $[x, y]$ 转化为：

• 固定部分 $w$：$x$ 和 $y$ 相同的那些高位。
• 自由部分：从 $p$ 位开始向下，可以任意组合，使得这一位为 1，且低位全为 1。

更具体地，设 $pref = (1 \ll (\text{highestBit}(x \oplus y) + 1)) - 1$，则：

$$w = y - (y \& pref)$$ $$r' = y \& pref$$ $$l' = x \& pref$$

其中 $w$ 是固定贡献，$r'$ 和 $l'$ 是自由区间。实际上 $r'$ 形如 $1000...$ 二进制，$l' = 0$。

代码中的 fix() 函数正是做这件事：

void fix() {
    for (int i = 0; i < n; ++i) {
        if (l[i] == r[i]) {
            w[i] = l[i];
            l[i] = r[i] = 0;
            continue;
        }
        int pref = (1 << (__lg(l[i] ^ r[i]) + 1)) - 1;
        w[i] = r[i] - (r[i] & pref);  // 固定高位部分
        r[i] &= pref;                  // 自由区间的右端点（形如 1000...0）
        l[i] &= pref;                  // 自由区间的左端点（0）
    }
}

2. 自由区间的性质

经过 fix() 后，每门课程变成：

• 固定贡献 $w_i$（必须贡献这些位）
• 一个自由区间 $[0, r_i]$，其中 $r_i$ 是形如 $1000...0$ 的二进制数（2 的幂）

这意味着：对于自由区间，我们可以独立选择该区间的任意子集位来设置为 1，但有一个关键限制：不能同时让最高位和某低位都为 1？不对，实际上对于区间 $[0, 2^k - 1]$ 我们可以任意组合，但这里 $r_i$ 是 $2^k$ 形式（比如 $1000_2$），所以区间是 $[0, 2^k]$ 吗？

仔细看：pref = (1 << (k+1)) - 1，其中 $k = \text{highestBit}(l \oplus r)$。那么 $r \& pref$ 是一个 $k+1$ 位二进制数，最高位（第 $k$ 位）为 1，低位任意。但由于 $l \& pref = 0$，实际上 $r \& pref$ 可以取 $2^k$ 到 $2^{k+1}-1$ 之间的值？代码中 r[i] &= pref 后，$r[i]$ 仍然可能不是 2 的幂。

实际上更简洁的理解：经过变换后，自由区间 $[0, r_i]$ 是一个完整的二进制前缀区间，我们可以独立决定每个位是否为 1。

贪心构造答案

对于查询 $[L, R]$（1-indexed 转 0-indexed）：

1. 固定贡献：所有课程固定部分 $w_i$ 的按位或，记作 ans = OR(w[L..R])。这部分必须包含。
2. 自由部分：每门课程还有一个自由区间 $[0, r_i]$，可以额外增加一些位。

问题转化为：已知当前 ans，每门课程还能额外提供一些位（但不能超过 $r_i$ 的位），问最多能再添加哪些位。

关键贪心策略

从高位到低位考虑（位 29 到 0）：

• 统计当前位在 ans 中是否已经为 1（来自固定部分）。
• 统计在区间 $[L, R]$ 内，有多少门课程的自由区间 $r_i$ 包含这一位（即 $r_i$ 的这一位为 1）。
• 设 cnt = 该位在自由区间中出现的次数 + (ans 中该位是否为 1)。

决策规则：

• 如果 cnt > 1：说明至少有 2 个来源可以提供这一位（包括可能已有的 ans），那么我们可以让这一位为 1，并且所有更低位都可以全部置为 1（因为我们可以让其中一个来源提供这一位，另一个来源提供低位全 1）。
• 如果 cnt == 1：这一位可以置为 1，但不能保证低位全为 1（因为只有一个来源）。
• 如果 cnt == 0：这一位无法置为 1。

算法实现细节

1. 数据结构

• 线段树：维护区间内 $w_i$ 的按位或（固定贡献）。
• 前缀和数组 bits[j][i]：表示前 $i$ 门课程中，自由区间 $r_i$ 的第 $j$ 位为 1 的个数。

2. 查询处理

int ans = t.get(x, y);  // 固定部分的 OR
for (int j = bit - 1; j >= 0; --j) {
    int cnt = bits[j][y] - bits[j][x] + (ans >> j & 1);
    if (cnt > 1) {
        ans |= (2 << j) - 1;  // 将第 j 位及以下所有位设为 1
        break;
    } else if (cnt == 1) {
        ans |= 1 << j;        // 只设置第 j 位
    }
}

3. 正确性解释

• 当 cnt > 1 时，至少有两个不同的来源可以产生第 $j$ 位。我们可以让其中一个提供第 $j$ 位，另一个提供第 $j$ 位以下的任意组合（通过选择适当的 $c_i$ 值），因此可以同时获得第 $j$ 位和所有低位。
• 当 cnt == 1 时，只有一个来源能提供第 $j$ 位，如果要这一位为 1，那个来源就不能再提供低位（因为它的自由区间是 $[0, r_i]$，选大值会失去低位），所以只能设置这一位，低位不能保证全 1。
• 一旦遇到 cnt > 1，就可以终止，因为低位都能自动获得。

时间复杂度

• 预处理：$O(n \cdot \text{bit})$，$\text{bit} = 30$。
• 每个查询：$O(\text{bit})$。
• 总复杂度：$O((n + q) \cdot 30)$，在 $2 \times 10^5$ 范围内完全可行。

完整代码注释版

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;
const int bit = 30;

// 线段树维护区间 OR
struct segtree {
    vector<int> t;
    int n;
    segtree(int n) : n(n) {
        t.resize(n * 2);
    }
    void upd(int i, int x) {
        for (t[i += n] = x; i > 1; i >>= 1) {
            t[i >> 1] = t[i] | t[i ^ 1];
        }
    }
    int get(int l, int r) {
        int res = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res |= t[l++];
            if (r & 1) res |= t[--r];
        }
        return res;
    }
};

int n;
int l[N], r[N], w[N];

// 将每个区间 [l, r] 分解为固定部分 w 和自由部分 [0, r']
void fix() {
    for (int i = 0; i < n; ++i) {
        if (l[i] == r[i]) {
            w[i] = l[i];
            l[i] = r[i] = 0;
            continue;
        }
        // 找到 l[i] 和 r[i] 最高的不同位
        int highest = __lg(l[i] ^ r[i]);
        int pref = (1 << (highest + 1)) - 1;  // 低 (highest+1) 位全 1
        w[i] = r[i] - (r[i] & pref);          // 高于 highest 的固定部分
        r[i] &= pref;                          // 自由部分上限
        l[i] &= pref;                          // 自由部分下限（实际为 0）
    }
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i];
    }
    fix();

    segtree seg(n);
    // bits[j][i] = 前 i 门课程中，第 j 位在自由区间中出现的次数
    vector<vector<int>> bits(bit, vector<int>(n + 1));

    for (int i = 0; i < n; ++i) {
        seg.upd(i, w[i]);  // 线段树存固定部分
        for (int j = 0; j < bit; ++j) {
            bits[j][i + 1] = bits[j][i];
            if ((r[i] >> j) & 1) {
                bits[j][i + 1]++;
            }
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        --x;  // 转为 0-indexed，区间 [x, y)
        int ans = seg.get(x, y);  // 固定部分的 OR

        // 贪心从高位到低位
        for (int j = bit - 1; j >= 0; --j) {
            int cnt = bits[j][y] - bits[j][x] + ((ans >> j) & 1);
            if (cnt > 1) {
                // 第 j 位可以置 1，且所有低位都能置 1
                ans |= (2 << j) - 1;
                break;
            } else if (cnt == 1) {
                ans |= (1 << j);
            }
        }
        cout << ans << " ";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

示例验证

以第二个测试用例为例：

• 课程1: [1,7] → 二进制 [001,111] → w=0, r=7 (111)
• 课程2: [1,7] → w=0, r=7
• 课程3: [3,10] → 二进制 [011,1010] → 最高不同位是 3（1000 vs 0011），w=0, r=10 (1010)
• 课程4: [2,2] → w=2, r=0

查询 [1,3]：w 的 OR = 0，自由位统计后贪心得到 15 (1111)。