E. Iva & Pav -前缀和 + 二分 +位运算

题面

分析：

赛时一直纠结于与运算前缀和不可逆，导致没有思路，但是发现行不通并没有及时思考别的解决办法导致一条路走到黑，阻碍了自己的思维，在今年的网络赛赛时也是一样，行不通的时候就没心思去重新想其他方法，这是大忌，以后要改，必须能够赛时不断发散自己思维，思考多种解决办法，还有就是赛时遇到一些自我感觉麻烦的做法就认为对的可能性不大，就不再去想，要大胆思考各种方法，多尝试。
虽然与运算不可逆，但是拆开他的每一位，从前向后记录他的每一位的1的个数，这样就可以进行前缀和计算了，根据后来的查询，只需要查询区间内的每一位的1的个数，只要区间内每一个数的二进制表示下第$i$位都是1，那么区间的与运算之和的第$i$位也就一定是1，这样就可以求出区间与运算的和，进而二分解决。

代码

#include 

using namespace std;
using ll = long long;

const int N = 2e5 + 10;

int a[N][32];
int n;
int L;
int k;

 bool check(int mid) {
    int cnt = 0;
    for(int i = 0; i <= 31; i ++) {
        //cout << a[mid][i] << ' ';
        if(a[mid][i] - a[L - 1][i] == mid - L + 1) cnt |= (1 << i);
    }
//   cout << mid << ' ' << cnt << endl;
    return cnt >= k;
 }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T --) {
        cin >> n;
        for(int i = 1; i <= n; i ++) {
            int x;
            cin >> x;
            for(int j = 0; j <= 31; j ++) {
                a[i][j] = a[i - 1][j] + (x >> j & 1);
            }
        }
        int q;
        cin >> q;
        while(q --) {
            cin >> L >> k;
            int l = L - 1;
            int r = n;
            while(l < r) {
                int mid = l + r + 1 >> 1;
                if(check(mid)) l = mid;
                else r = mid - 1;
            }
            if(l < L || l > n) cout << "-1 ";
            else cout << l << " ";
            //cout << endl;
        }
        cout << "\n";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55