1 条题解

  • 0
    @ 2026-11-15 22:53:17

    由于不同二进制位间互不干扰,可以将每个数字拆成各位进行分别处理。

    • 对于按位异或,统计区间内每一位上 1 的个数,若该数为奇数,则该位为 1。
    • 对于按位或,某一位只要区间内出现过 1,该位就为 1。
    • 对于按位与,某一位要求区间内全部为 1,该位才为 1。

    可以对每一位分别做前缀和预处理,整体时间复杂度为 O((n+m)log⁡V)\mathcal O((n + m) \log V),其中 VV 为值域。

    代码:

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    int main() {
    	int n, q;
    	cin >> n >> q;
    	vector<int> arr(n + 1);
    	vector<vector<int>> bit(n + 1, vector<int>(21));
    	for(int i = 1; i <= n; ++i){
    		cin >> arr[i];
    		for(int j = 0; j <= 20; ++j){
    			bit[i][j] = bit[i-1][j] + ((arr[i] >> j) & 1);
    		}
    	}
    	while(q--){
    		int op, l, r;
    		cin >> op >> l >> r;
    		int res = 0;
    		for(int j = 0; j <= 20; ++j){
    			int cnt = bit[r][j] - bit[l-1][j];
    			if(op == 1){
    				if(cnt & 1) res |= (1 << j);
    			}else if(op == 2){
    				if(cnt > 0) res |= (1 << j);
    			}else{
    				if(cnt == r - l + 1) res |= (1 << j);
    			}
    		}
    		cout << res << '\n';
    	}
    }
    
    • 1

    信息

    ID
    224
    时间
    2000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者