【异或和之和 / H】

题目

思路

• 异或前缀和优化到 
  • 计算本身是，这很好
  • 单用前缀和的缺点是我们按照枚举  对计算贡献，分的种类也就是计算的次数达到了 
  • 优化方式是，我们按照枚举各个数位  来计算贡献，这样时间就会达到 
• 拆位法+贡献法
  • 有贡献的是  异或
  • 第  位（从0开始）上的  有序对数目乘以权重  就是对答案的贡献

代码 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;const int N = 1e5+10;
int s[N];
ll ans;
int main()
{int n;cin >> n;for(int i = 1; i <= n; i++)cin >> s[i], s[i] = s[i] ^ s[i-1];for(int i = 0; i < 21; i++){ll now = 0;int c0 = 0, c1 = 0;for(int j = 0; j <= n; j++){if((s[j] >> i) & 1) now += c0, c1++;else now += c1, c0++;}ans += now * (1 << i);}cout << ans;
}