1 条题解
-
0
由于不同二进制位间互不干扰,可以将每个数字拆成各位进行分别处理。
- 对于按位异或,统计区间内每一位上
1的个数,若该数为奇数,则该位为1。 - 对于按位或,某一位只要区间内出现过
1,该位就为1。 - 对于按位与,某一位要求区间内全部为
1,该位才为1。
可以对每一位分别做前缀和预处理,整体时间复杂度为 ,其中 为值域。
代码:
#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'; } } - 对于按位异或,统计区间内每一位上
信息
- ID
- 224
- 时间
- 2000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者