题解 CF1665E 【MinimizOR】

enucai · 2022-04-09 08:24:57 · 题解

Analysis

线段树解法。

结论：\min\limits_{l\le i<j\le r} a_i|a_j 的 a_i 与 a_j 一定是 [l,r] 区间内的前 31 小数中的 2 个。

证明：采用数学归纳法。原命题 \Leftrightarrow 小于 2^k 的数中的 \operatorname{OR} 最小值出现在前 k+1 小数中的两个数之间。

对于 k=1，结论显然成立。

对于 k>1：

1. 若当前最高位有 \ge 2 个 0，根据高位贪心策略，当前位选 0，最小值一定是 k-1 位的最小值，一定在前 k 小值中。

2. 若当前为高位没有 0，则只能选一，结果是 k-1 位中的最小值 +2^{k-1}，也一定在前 k 小值中。

3. 若当前位有 1 个 0，当前位一定是 1，找当前位为 1 的最小值一定在前 k 个当前位为 1 的数中，加上一个当前位为 0 的。因此一定在前 k+1 小值中。

用线段树维护区间最小值，每次询问找到区间前 31 小值，暴力枚举统计即可。时间复杂度 O(31^2\cdot q\cdot \log n)。

Code

Talk is cheap, show me the code.

Codeforces Status

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid (l+r)/2
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define Rof(i,j,k) for(int i=(j);i>=(k);i--)
pair<int,int> tr[400010];
void upd(int c,int l,int r,int x,int val){
    if(l==r){
        tr[c]=make_pair(val,x);
        return;
    }
    if(x<=mid) upd(c*2,l,mid,x,val);
    else upd(c*2+1,mid+1,r,x,val);
    tr[c]=min(tr[c*2],tr[c*2+1]);
}
pair<int,int> qry(int c,int l,int r,int x,int y){
    if(l==x&&r==y) return tr[c];
    else if(y<=mid) return qry(c*2,l,mid,x,y);
    else if(x>mid) return qry(c*2+1,mid+1,r,x,y);
    else return min(qry(c*2,l,mid,x,mid),qry(c*2+1,mid+1,r,mid+1,y));
}
int n,q,a[100010];
vector<pair<int,int> > now;
void work(){
    cin>>n;
    For(i,1,n) cin>>a[i];
    For(i,1,n) upd(1,1,n,i,a[i]);
    cin>>q;
    while(q--){
        int l,r;cin>>l>>r;
        now.clear();int lim=min(r-l+1,31ll);
        For(i,1,lim) now.push_back(qry(1,1,n,l,r)),upd(1,1,n,now.back().second,(1ll<<31));
        int mn=(1ll<<31);
        For(i,0,now.size()-1) For(j,i+1,now.size()-1) mn=min(mn,now[i].first|now[j].first);
        cout<<mn<<endl;
        for(auto p:now) upd(1,1,n,p.second,a[p.second]);
    }
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int T;cin>>T;
    while(T--) work();
}