CF1878E Iva & Pav

CF 是没题考了吧，每场都出二进制拆位。

思路

首先我们可以二分 $r$，因为 $r$ 越大，按位与一定只会小于等于 $r$ 小的情况。

那么，我们可以用 $num_{i,j}$ 记录 $a_j$ 第 $i$ 位的二进制情况。

如果我们对 $num_{i,j}$ 做一个前缀和，如果 $num_{i,r} - num_{i,l - 1} = r - l + 1$，说明 $[l,r]$ 中第 $i$ 位都是 $1$，那么它对按位与的贡献就有 $2^i$。

Code

#include <bits/stdc++.h>  
#define re register  
#define int long long  
  
using namespace std;  
  
const int N = 2e5 + 10,M = 34;  
int T,n,q;  
int arr[N];  
int num[M][N];  
  
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;  
}  
  
inline bool check(int l,int r,int k){  
    int sum = 0;  
    for (re int bit = 0;bit <= 30;bit++){  
        int cnt = num[bit][r] - num[bit][l - 1];  
        if (cnt == r - l + 1) sum += (1ll << bit);  
    }  
    return (sum >= k);  
}  
  
signed main(){  
    T = read();  
    while (T--){  
        n = read();  
        for (re int i = 0;i <= 30;i++){  
            for (re int j = 1;j <= n;j++) num[i][j] = 0;  
        }  
        for (re int i = 1;i <= n;i++){  
            arr[i] = read();  
            for (re int bit = 0;bit <= 30;bit++){  
                if (arr[i] >> bit & 1) num[bit][i] = 1;  
                num[bit][i] += num[bit][i - 1];  
            }  
        }  
        q = read();  
        while (q--){  
            int l,L,r = n,x;  
            L = l = read();  
            x = read();  
            while (l < r){  
                int mid = l + r + 1 >> 1;  
                if (check(L,mid,x)) l = mid;  
                else r = mid - 1;  
            }  
            if (check(L,l,x)) printf("%lld ",l);  
            else printf("-1 ");  
        }  
        puts("");  
    }  
    return 0;  
}