题目描述
难度分:$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;
}