题目描述

难度分:$2500$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$，$q$之和$\leq 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(0 \leq a[i] \lt 2^{30})$。数组下标从$1$开始。

然后输入$q(1 \leq q \leq 10^5)$和$q$个询问，每个询问输入两个数$L$和$R$，表示下标从$L$到$R$的连续子数组 $(1 \leq L \lt R \leq n)$。

对于每个询问，输出子数组内两个下标不同的数的$OR$的最小值。

输入样例

2
5
6 1 3 2 1
4
1 2
2 3
2 4
2 5
4
0 2 1 1073741823
4
1 2
2 3
1 3
3 4

输出样例

7
3
3
1
2
3
1
1073741823

算法

数学归纳法+线段树

这个题真的很难，需要从特殊推广到一般，猜结论。结论就是$2^n$次方以内的数，要想求得两个数按位或的最小值，至少需要知道最小的$n+1$个数。这个结论是举例猜出来然后证明的，瞪眼是看不出来的。而本题的数值范围在$2^{30}$以内，因此只需要知道子数组$[L,R]$内最小的$31$个数，就能以$C_{31}^{2}$的常数枚举操作求得子数组$[L,R]$中的答案。

最后就是区间$topk$如何求解？我们可以用线段树来维护这个信息，线段树的每个节点都存储自己覆盖子数组内的$top31$的最小数。当两个节点合并时，可以先合并两个节点的$top$元素，然后再用快速选择算法选出新的$top31$，这样合并信息的时间复杂度就是线性的。

复杂度分析

时间复杂度

构建线段树的时间复杂度为$O(nlog_2n)$，每个询问都是先进行一次线段树的查询，时间复杂度为$O(log_2Alog_2n)$，其中$A=2^{30}$。最后还要$C_{31}^{2}$枚举数对，可以粗略地看成是一个很大的常数。因此算法整体的时间复杂度为$O(nlog_2n+qlog_2Alog_2n)$。

空间复杂度

瓶颈在于线段树的消耗，额外空间复杂度是$O(n)$的。但由于线段树的节点需要存储$topk$的数组，所以常数会比一般的线段树大很多。

参考文献

结论的证明以及最优解的构造方法学习了灵佬的题解，详见灵茶山艾府的题解 。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 100010;
int t, n, q, l, r;

class SegmentTree {
public:
    const int k = 31;
    int a[N];
    struct Info {
        int l, r;
        vector<int> topk;
        Info() {}
        Info(int left, int right, int val): l(left), r(right) {
            topk.push_back(val);
        }
    } seg[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            seg[u] = Info(l, r, a[r]);
        }else {
            int mid = l + r >> 1;
            build(u<<1, l, mid);
            build(u<<1|1, mid + 1, r);
            pushup(u);
        }
    }

    Info query(int l, int r) {
        if(l > r) return Info(0, 0, 0);
        return query(1, l, r);
    }

private:
    Info query(int u, int l, int r) {
        if(l <= seg[u].l && seg[u].r <= r) return seg[u];
        int mid = seg[u].l + seg[u].r >> 1;
        if(r <= mid) {
            return query(u<<1, l, r);
        }else if(mid < l) {
            return query(u<<1|1, l, r);
        }else {
            return merge(query(u<<1, l, r), query(u<<1|1, l, r));
        }
    }

    void pushup(int u) {
        seg[u] = merge(seg[u<<1], seg[u<<1|1]);
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.l = lchild.l;
        info.r = rchild.r;
        vector<int> vals;
        for(int num: lchild.topk) {
            vals.push_back(num);
        }
        for(int num: rchild.topk) {
            vals.push_back(num);
        }
        int m = min(k, (int)vals.size());
        nth_element(vals.begin(), vals.begin() + m, vals.end());
        for(int i = 0; i < m; i++) {
            info.topk.push_back(vals[i]);
        }
        return info;
    }
};

int main() {
    scanf("%d", &t);
    SegmentTree seg;
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &seg.a[i]);
        }
        seg.build(1, 1, n);
        scanf("%d", &q);
        while(q--) {
            scanf("%d%d", &l, &r);
            auto v = seg.query(l, r).topk;
            int ans = v[0]|v[1], m = min(31, (int)v.size());
            for(int i = 0; i < m; i++) {
                for(int j = i + 1; j < m; j++) {
                    if((v[i]|v[j]) < ans) ans = v[i]|v[j];
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}