喵~ 各位算法大师们好呀，我是你们的小助手猫娘~ 今天要给大家带来的是一道关于位运算和数据结构的题目，Iva & Pav (Problem 1878E) 的题解喵。Pav 为了让 Iva 开心，可是什么都愿意做呢！我们也要帮帮他，让他能快点解决 Iva 的问题，这样他就能陪 Iva 玩啦，嘿嘿~

题目大意

这道题是说呀，Iva给了她亲爱的 Pav 一个长度为 n 的数组 a。然后她定义了一个函数 f(l, r)，这个函数的值是数组 a 从下标 l 到 r 的所有元素的按位与（bitwise AND）的结果，也就是 a[l] & a[l+1] & ... & a[r]。

接下来，Iva 会给出 q 个询问。每个询问包含两个数字 l 和 k。对于每个询问，Pav 需要找到一个最大的下标 r (其中 l ≤ r ≤ n)，使得 f(l, r) 的值大于等于 k。如果找不到这样的 r，就要输出 -1。

简单来说，就是对于每个给定的 l 和 k，我们要找一个最靠右的 r，让从 a[l] 到 a[r] 这一段区间的“与和”不小于 k。

解题思路

拿到这道题，我们先来分析一下 f(l, r) 这个函数的性质喵。

按位与 & 有一个非常重要的特性：当一个数字与上另一个数字时，它的值只会变小或者不变，绝对不会变大。这是因为 & 运算只有在两个位都是1时结果才是1，否则就是0。所以，x & y <= x 并且 x & y <= y 总是成立的。

那么，对于我们这个函数 f(l, r) = a[l] & ... & a[r]，当我们固定左端点 l，然后慢慢增大右端点 r 时，f(l, r) 的值会怎么样呢？

• f(l, l) = a[l]
• f(l, l+1) = f(l, l) & a[l+1]
• f(l, l+2) = f(l, l+1) & a[l+2]
• ...

看到了吗？f(l, r+1) 就是 f(l, r) 再与上一个新的数 a[r+1]。根据我们刚才说的性质，f(l, r+1) <= f(l, r)。所以，随着 r 的增加，f(l, r) 的值是单调不增的！

这个单调性可是个超级棒的性质呀，喵~！它告诉我们，对于一个固定的 l 和 k：

• 如果我们找到了一个 r 使得 f(l, r) >= k，那么对于所有 r' < r，也一定有 f(l, r') >= k。
• 如果我们找到了一个 r 使得 f(l, r) < k，那么对于所有 r' > r，也一定有 f(l, r') < k。

这不就是二分搜索最喜欢的场景嘛！我们可以对答案 r 进行二分搜索。

对于每个询问 (l, k)，我们可以在 [l, n] 这个范围内二分查找最大的 r。

1. 设定二分搜索的区间 [low, high]，初始为 [l, n]。
2. 取中间值 mid = low + (high - low) / 2。
3. 计算 f(l, mid) 的值。
4. 如果 f(l, mid) >= k，说明 mid 是一个合法的解，但可能还有更大的 r 也满足条件。所以我们记录下这个 mid，然后尝试在右半部分 [mid+1, high] 继续寻找。
5. 如果 f(l, mid) < k，说明 mid 太大了，导致“与和”变得太小了。我们需要减小 r，所以在左半部分 [low, mid-1] 中寻找。

二分搜索的框架有了，但还有一个问题：我们怎么在二分的过程中快速计算 f(l, mid)，也就是一个区间的按位与和呢？如果每次都用一个循环去算，那每次查询就是 O(n log n)，太慢了，Pav 会等不及的！

这里就需要一个能快速处理静态区间查询的数据结构了。因为按位与 & 满足结合律（(a&b)&c = a&(b&c)），所以我们可以用稀疏表 (Sparse Table, ST表) 来解决这个问题。

ST表可以在 O(n log n) 的时间内完成预处理，之后每次查询一个区间的与和只需要 O(1) 的时间。这简直是为我们量身定做的呀！

所以，我们的最终策略就是：

1. 预处理：对整个数组 a 构建一个 ST 表，用来快速查询任意区间的按位与和。时间复杂度 O(n log n)。
2. 处理查询：对于每个查询 (l, k)，在 [l, n] 上二分搜索答案 r。在二分的每一步中，使用 ST 表在 O(1) 时间内计算区间 [l, mid] 的与和，并根据结果调整二分范围。单次查询时间复杂度 O(log n)。

总的时间复杂度就是 O(n log n + q log n)，对于这道题的数据范围来说，是完全可以接受的喵~

题解代码

下面就是参考的 C++ 代码实现啦，本猫娘在代码里加了一些注释，方便大家理解哦。

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

// 这是一个加速输入输出的小魔法，让程序跑得更快喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

// 根据题目限制定义常量
const int MAXN = 200005;
const int LOGN = 18; // log2(200005) 向上取整是 18

// ST 表本体和预计算 log 的数组
int st[MAXN][LOGN];
int log_table[MAXN];

// 处理单个测试用例的函数
void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // --- ST 表预处理 O(n log n) ---
    // st[i][j] 存储的是从下标 i 开始，长度为 2^j 的区间的与和
    for (int i = 0; i < n; ++i) {
        st[i][0] = a[i]; // 长度为 1 (2^0) 的区间就是它自己
    }
    for (int j = 1; j < LOGN; ++j) {
        for (int i = 0; i + (1 << j) <= n; ++i) {
            // 一个大区间可以由两个一半大小的区间合并而成
            st[i][j] = st[i][j - 1] & st[i + (1 << (j - 1))][j - 1];
        }
    }

    int q;
    std::cin >> q;
    while (q--) {
        int l, k;
        std::cin >> l >> k;
        --l; // 题目是 1-based，我们转成 0-based 好处理

        // 特殊情况：如果第一个数 a[l] 就比 k 小，那肯定找不到答案啦
        if (a[l] < k) {
            std::cout << -1 << " ";
            continue;
        }

        // --- 二分搜索答案 r ---
        int low = l, high = n - 1;
        int ans = l; // 答案至少是 l

        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            // --- ST 表查询 O(1) ---
            // 查询区间 [l, mid] 的与和
            int len = mid - l + 1;
            int j = log_table[len]; // 找到小于等于 len 的最大 2 的幂次
            int current_and = st[l][j] & st[mid - (1 << j) + 1][j];

            if (current_and >= k) {
                // mid 满足条件，它是一个可能的答案，我们尝试找更大的 r
                ans = mid;
                low = mid + 1;
            } else {
                // mid 不满足条件，说明 r 太大了，要往左边找
                high = mid - 1;
            }
        }
        std::cout << ans + 1 << " "; // 输出时转回 1-based
    }
    std::cout << "\n";
}

int main() {
    fast_io();

    // 预计算 log_table，这样 ST 查询时就能 O(1) 得到 j
    log_table[1] = 0;
    for (int i = 2; i < MAXN; ++i) {
        log_table[i] = log_table[i / 2] + 1;
    }

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题用到了几个很有用的知识点，我们来一起复习一下吧，喵~

1. 位运算 (Bitwise Operations)

• 按位与 (&): 这是一个二进制运算。对于两个整数的每一个二进制位，只有当两个数的对应位都为 1 时，结果的该位才为 1，否则为 0。
  • 例如: 15 & 14
    • 15 的二进制是 ...00001111
    • 14 的二进制是 ...00001110
    • & 运算结果是 ...00001110，也就是 14。
• 关键性质: x & y <= min(x, y)。这个性质导致了我们函数 f(l, r) 的单调性，是解题的突破口。

2. 单调性与二分搜索 (Monotonicity & Binary Search)

• 单调性: 指的是一个函数随着自变量的增加，函数值总是朝一个方向变化（一直增加或一直减少）。
• 二分搜索: 是一种在有序或具有单调性的集合中查找特定元素的算法。它通过不断将搜索区间减半来快速定位目标。只要你发现问题满足“如果 x 可以，那么比 x 更‘小’的也都可以”或者“如果 x 不行，那么比 x 更‘大’的也都不行”这样的性质，就可以考虑二分搜索啦！

3. 稀疏表 (Sparse Table / ST 表)

• 是什么: ST 表是一种用于高效回答静态数组上区间查询问题的数据结构。静态意味着数组在查询过程中不会被修改。
• 适用场景: 它特别适用于那些满足结合律和幂等性的查询操作。
  • 结合律: (a op b) op c = a op (b op c)。例如加法、乘法、最大值、最小值、按位与、按位或。
  • 幂等性: a op a = a。例如最大值、最小值、按位与、按位或。
• 原理: ST 表通过 O(n log n) 的预处理，将所有长度为 2^j 的区间的查询结果都计算并存储起来。st[i][j] 通常表示从 i 开始，长度为 2^j 的区间 [i, i + 2^j - 1] 的计算结果。
• 查询: 查询任意区间 [l, r] 时，我们可以找到一个 j 使得 2^j 是小于等于区间长度 r-l+1 的最大2的幂。然后我们将区间 [l, r] 覆盖为两个长度为 2^j 的、有重叠的子区间：[l, l + 2^j - 1] 和 [r - 2^j + 1, r]。将这两个预计算好的结果合并（做一次 op 操作），就是整个区间的答案。对于满足幂等性的操作，重叠部分计算两次也没关系，所以查询是 O(1)。对于我们这题的按位与，它也是幂等的 (x & x = x)，所以完美适用！

好啦，今天的题解就到这里啦！希望这篇讲解能帮到大家。只要发现了函数的单调性，再联想到用合适的数据结构来优化查询，问题就迎刃而解了呢！大家要继续加油哦，喵~ ❤