题解：CF1983F array-value

· · 题解

这里提供一种比较好写的时间复杂度 O(n\log V) 的做法。

套路地，对于求第 k 小问题，通过二分答案转化成求 < x 的方案数问题。直接做并不好做，考虑扫描线，记录每个点为右端点时的最优左端点，于是只需要考虑单个数的匹配。

注意到 a_i \oplus a_j <x 的左侧异或和并不好做，转而对右侧进行拆分，对于其二进制的第 k 位的 1，将贡献拆成“要求异或和的 k 位之前与 x 相同，第 k 位为 0，其余无要求”。

0 的限制是平凡的，只需要这几位都取相同即可；对于 1 的限制，注意到这一位的取 0 或 1 均无关，所以等价于无限制。此时我们只要对于拆成的每个贡献计算只保留元素对应 0 位的二进制值即可，此时问题等价于求等值前驱，容易维护。此时时间复杂度 O(n\log^2 V)。

考虑在二进制问题中二分答案的另一种表现形式，拆位贪心。当我们从高到低逐位考虑时，每次只会加入 1 条限制，直接在匹配数组上取最大值即可，单次只需要扫一次数组。

用哈希表实现前驱，时间复杂度 O(n\log V)。

#include<bits/stdc++.h>
#define maxn 510005
#define int long long
using namespace std;

int n,k,a[maxn],pre[maxn];
unordered_map<int,int>mp;
int check(int x){
    mp.clear();
    int res=0,maxx=0;
    for(int i=1;i<=n;i++){
        int cur=a[i]&x;
        maxx=max(maxx,pre[i]);
        if(mp.count(cur)) maxx=max(maxx,mp[cur]);
        mp[cur]=i;
        res+=maxx;
        if(res>=k) return 0;
    }
    return 1;
}
void update(int x){
    mp.clear();
    for(int i=1;i<=n;i++){
        int cur=a[i]&x;
        pre[i]=max(pre[i],pre[i-1]);
        if(mp.count(cur)) pre[i]=max(pre[i],mp[cur]);
        mp[cur]=i;
    }
}
void solve(){
    int x=0;
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),pre[i]=0;
    for(int i=30;i>=0;i--){
        if(check(~(x|((1<<i)-1)))) update(~(x|((1<<i)-1))),x|=(1<<i);
    }
    printf("%lld\n",x);
}
signed main(){
    signed T=1;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}