思路
发现 \(2^k\) 大的数,最终的答案一定由前 \(k + 1\) 小的元素组成。
考虑数学归纳法,显然当 \(k = 1\) 成立。假令 \(k'\) 时成立,证明 \(k = k' + 1\) 时成立即可:
-
若第 \(k\) 位有两个及以上的 \(0\),显然最终答案的第 \(k\) 位一定为 \(0\),因此考虑前面的 \(k - 1\) 位,显然取前 \(k + 1\) 小的数是对的。
-
若第 \(k\) 位只有一个 \(0\),显然最终答案的第 \(k\) 位一定为 \(1\),因此考虑前面的 \(k - 1\) 位,显然取前 \(k + 1\) 小的数成立。
-
若第 \(k\) 位没有 \(0\),显然最终答案的第 \(k\) 位一定为 \(1\),考虑前 \(k - 1\) 位,显然取前 \(k + 1\) 小的数可以。
因此我们不妨使用线段树维护区间前 \(31\) 小。
Code
#include <bits/stdc++.h>
#define re register
#define int long long
using namespace std;
const int N = 1e5 + 10,inf = (int)(1e18) + 10;
int n,q;
int arr[N];
vector<int> emp;
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
struct seg{
#define ls(u) (u << 1)
#define rs(u) (u << 1 | 1)
struct value{
vector<int> v;
value friend operator +(const value &a,const value &b){
value v;
for (auto x:a.v) v.v.push_back(x);
for (auto x:b.v) v.v.push_back(x);
sort(v.v.begin(),v.v.end());
while (v.v.size() > 31) v.v.pop_back();
return v;
}
};
struct node{
int l,r;
value val;
}tr[N << 2];
inline void pushup(int u){
tr[u].val = tr[ls(u)].val + tr[rs(u)].val;
}
inline void build(int u,int l,int r){
tr[u] = {l,r,{emp}};
if (l == r) return tr[u].val.v.push_back(arr[l]),void();
int mid = l + r >> 1;
build(ls(u),l,mid),build(rs(u),mid + 1,r);
pushup(u);
}
inline auto query(int u,int l,int r){
if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;
int mid = tr[u].l + tr[u].r >> 1;
value res = {emp};
if (l <= mid) res = res + query(ls(u),l,r);
if (r > mid) res = res + query(rs(u),l,r);
return res;
}
#undef ls
#undef rs
}T;
inline void solve(){
n = read();
for (re int i = 1;i <= n;i++) arr[i] = read();
T.build(1,1,n);
q = read();
while (q--){
int l,r,ans = inf;
l = read(),r = read();
vector<int> res = T.query(1,l,r).v;
int len = res.size();
for (re int i = 0;i < len;i++){
for (re int j = i + 1;j < len;j++) ans = min(ans,res[i] | res[j]);
}
printf("%lld\n",ans);
}
}
signed main(){
int T;
T = read();
while (T--) solve();
return 0;
}
标签:MinimizOR,int,题解,CF1665E,value,re,while,显然,res
From: https://www.cnblogs.com/WaterSun/p/18264796