位运算技巧之拆位

1：Codeforces Round 900 (Div. 3) ：E. Iva & Pav

题意：给出一个长度为n的数组，给出一个l和k，求连续与运算之后找出最大的一个r，使得f(l,r)运算之后得出的结果大于等于k

思路：这里使用拆位的技巧，根据数据范围可知数字表示为二进制后最大不会超过32位，那我们预处理记录出每一位的1的数量，然后求前缀和，只有(r - l + 1)这个区间的1的数量为（r - l + 1)的时候这个位才会产生贡献，贡献也就是2^k(k指的是所处的位置），然后就可以求出这个[l, r]区间的与运算之后的值。 我们根据与运算的性质可知结果是有单调性的，所以我们可以通过二分来处理答案

#include<bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
//#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N = 200010, mod = 998244353;
const int Mod = 1e9 + 7, INF = 0x3f3f3f3f;

vector<vector<int> > v(N, vector<int>(35, 0));
int a[N];

bool check(int l, int r, int x){
	int sum = 0;
	for(int i = 0; i <= 32; i ++){
		int p = v[r][i] - v[l - 1][i];
		if(p == r - l + 1) sum += 1ll << i;
	}
	
	return sum >= x;
}
void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	
	for(int i = 1; i <= n; i ++){
		for(int j = 0; j <= 32; j ++){
			v[i][j] = a[i] >> j & 1;
		}
	}//按位记录1的数量 
	
	for(int i = 1; i <= n; i ++){
		for(int j = 0; j <= 32; j ++){
			v[i][j] += v[i - 1][j];
		}
	}//求出1的数量的前缀 
	
	int m;
	cin >> m;
	while(m --){
		int l1, k;
		cin >> l1 >> k;
		int l = l1, r = n;
		while(l <= r){
			int mid = l + r >> 1;
			if(check(l1, mid, k)) l = mid + 1;
			else r = mid - 1;
		}
		if(r < l1) r = -1;
		cout << r << ' ';
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while(t --){
		solve();
		cout << '\n';
	}
	return 0;
}