题目
D - Xor Sum 2
给出n个元素的数组a,求满足条件的子区间个数:数组a子区间元素和与异或和相等。
思路
- 和与异或和相同,即没有任何进位,也就是区间中对于范围内每个二进制位,最多出现一次;
- 使用双指针,统计每个二进制位最多出现一次的区间个数即可;
总结
- 异或:不进位加法;
代码
点击查看代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;
const int N = 2e5 + 10;
int a[N];
void solv()
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
LL ans = 0;
for (int l = 1, r = 0, t = 0; l <= n; l ++)
{
while (r + 1 <= n && ((t & a[r + 1]) == 0))
{
r ++;
t |= a[r];
}
t ^= a[l];
ans += r - l + 1;
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
solv();
return 0;
}