CF1935E 题解

sunkuangzheng · 2024-03-06 07:56:57 · 题解

• 给定序列 \{x_n\},\{y_n\}，共有 q 组询问，第 i 组询问给出 l,r，你需要构造序列 a 满足 a_i \in [x_i,y_i]，求 \max \operatorname{OR}_{i=l}^r a_i。

提示 1

考虑对于一对 (x_i,y_i)，如果 y_i 的第 k 位是 1 则答案第 k 位一定是 1，思考为什么。

提示 2

如果所有 (x_i,y_i) 的最高位不同该怎么做？

题解

首先我们对于每一对 (x_i,y_i)，去除它们二进制下最长公共前缀并直接算入答案 ans，此时一定满足 x_i < y_i 且最高位不同。考虑对于某一位 j，考虑区间内有多少 y_i 满足 y_i 的第 j 位是 1，加上 ans 的第 j 位是否是 1 后假设有 c 个：

你也可以通过以上流程发现，在去除最长公共前缀后 x_i 就已经没有意义，因为当 c \ge 2 时我们直接得到答案，c= 1 时只关心能否在某一位填 1，而这个与 x_i 无关。

可以前缀和统计出现次数，ST 表维护区间或，时间复杂度 \mathcal O((n+q) \log nV)。

/**
 *    author: sunkuangzheng
 *    created: 06.03.2024 07:28:11
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n,q,x,y,l,r;
void los(){
    cin >> n;
    vector<vector<int>> ct(36,vector<int>(n + 1)),st(25,vector<int>(n + 1));
    for(int i = 1;i <= n;i ++){
        cin >> x >> y;
        for(int j = 30;j >= 0;j --)
            if(((x >> j) & 1) == ((y >> j) & 1)) st[0][i] |= (((x >> j) & 1) << j);
            else{
                for(int k = j;k >= 0;k --) if((y >> k) & 1) ct[k][i] ++;
                break;
            }
        for(int j = 30;j >= 0;j --) ct[j][i] += ct[j][i-1];
    }for(int j = 1;j <= __lg(n);j ++) for(int i = 1;i + (1 << j) - 1 <= n;i ++)
        st[j][i] = st[j-1][i] | st[j-1][i + (1 << j-1)];
    auto qry = [&](int l,int r){
        int k = __lg(r - l + 1);
        return st[k][l] | st[k][r-(1<<k)+1];
    };
    cin >> q;
    while(q --){
        cin >> l >> r;
        int ans = qry(l,r),w;
        for(int i = 30;i >= 0;i --)
            if(w = ct[i][r] - ct[i][l-1] + ((ans >> i) & 1),w >= 2) ans |= (1 << i + 1) - 1;
            else if(w) ans |= (1 << i); 
        cout << ans << " ";
    }cout << "\n";
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}