题目E. MinimizOR

前置知识：线段树求区间最值、理论（如果所有的数字都小于 $2^k$ ，那么考虑区间中k+1个最小的数字就可以找出 ${\min }_{i\ne j}{a}_i|a_j$ ）

证明：来源于官方题解

归纳法

如果所有的数字都小于$2^k$，那么考虑$k+1$个最小的数字就足够了。

基本情况：$k=1$，所有的数字都是从 $0$ 到 $1$ ，证明很明显。

归纳的步骤。

让我们来证明，对于任何 $k\ge 1$ 的情况，如果对于 $k$ 来说声明是真的，那么对于 $k+1$也是真的。

如果所有数字的第 $k$ 位都是 $1$，那么答案的第 $k$ 位也是 $1$，这就是为什么我们只需要最小化剩下的位。对于这些位，我们可以应用归纳假设，即 $k+1$ 个最小的数字就足够了。如果至少有两个数字的第 $k$ 位是 $0$ ，那么答案的第 $k$ 位也是 $0$ ，这就是为什么我们只考虑第 $k$ 位是 $0$ 的数字，我们必须最小化其余的位。再次应用归纳假设，$k+1$ 个最小的数字就足够了。如果正好有一个数字的第$k$ 位是 $0$ ，那么答案中的第 $k$ 位就是 $1$ ，我们必须在 $k$ 位上找到 $k+1$ 个最小数。他们是 $k+2$ 个在 $k+1$ 位上的最小数，所以 $k+2$ 个最小数足够了。

在有了前面的理论基础，剩下的可以用线段树求区间中 $k+1$ 个最小值。

注：$k$ 不超过 $30$

#include<stdio.h>
#include<algorithm>using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
struct node{int l,r;ll min[40];
}tr[N * 4];
ll res[40];void down(int p) {ll b[70];int L = 0;for(int i=0;i<=32;i++) b[L ++] = tr[p*2].min[i];for(int i=0;i<=32;i++) b[L ++] = tr[p*2+1].min[i];sort(b,b+L);for(int i=0;i<=32;i++) tr[p].min[i] = b[i];
}void build(int p,int l,int r) {tr[p].l = l,tr[p].r = r;for(int i=0;i<=32;i++) tr[p].min[i] = 1e15;if(l == r) {scanf("%lld",&tr[p].min[0]);return ;}int mid = (l + r) >> 1;build(p*2,l,mid);build(p*2+1,mid+1,r);down(p);
}void ask(int p,int l,int r) {if(tr[p].l >= l && r >= tr[p].r) {ll b[70];int L = 0;for(int i=0;i<=32;i++) b[L ++] = tr[p].min[i];for(int i=0;i<=32;i++) b[L ++] = res[i];sort(b,b+L);for(int i=0;i<=32;i++) res[i] = b[i];return ;}int mid = (tr[p].l + tr[p].r) >> 1;if(l <= mid) ask(p*2,l,r);if(r > mid) ask(p*2+1,l,r);
}int main(){int t;scanf("%d",&t);while(t --) {int n;scanf("%d",&n);build(1,1,n);int m;scanf("%d",&m);while(m --) {int l,r;scanf("%d %d",&l,&r);for(int i=0;i<=32;i++) res[i] = 1e15;ask(1,l,r);ll ans = 1e15;for(int i=0;i<=32;i++) {for(int j=i+1;j<=32;j++) {ans = min(ans,res[i] | res[j]);}}printf("%lld\n",ans);}}return 0;
}