[BZOJ4017] 小Q的无敌异或（异或, 树状数组）

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4017

（这是一道好题）给你n个数，分别问这n个数中任意两个区间的异或和的加和是多少、任意两个区间的和的异或和是多少。

Task 1：求异或的和

针对第一问，我们首先分析出两个性质：

设 $[1,i]$ 的异或和为 $xor[i]$ ，那么区间 $[l,r]$ 内数字的异或和为 $xor[l-1]⨁xor[r]$ 。
某个在数字第k位有贡献的子区间 $[l,r]$ ，它们的前缀异或和 $xor[l]$ 与 $xor[r]$ 的值一定不同。而且很显然，这个区间的贡献为 $2^k$ 。

有上述的两个性质，我们的目标其实就是拆分数位，针对每个数位，找到整个 $[1,n]$ 区间内有多少对前缀异或和结果不同。假设在 $[1,n]$ 中的第 $k$ 位数字有 $x$ 个数该位是 $1$ ，那么就有 $n-x$ 个位置是 $0$ 。这样只是找到了区间长度≥2的贡献，但是题目规定单个数字也算贡献，不妨再加上一个 $x$ ，问题转化成在两个数字集合中分别挑选一个数字，问有多少对数字，因此第 $k$ 位总体贡献是 $x(n-x+1)2^k$ 。

实现就很简单，我们针对每一位 $k$ ，求异或和的每一步时，更新这个 $x$ ，最后算一下贡献就行了。

LL gao1() {
  LL ret = 0;
  for(int k = 0; k < 20; k++) {
    int cur = 0, cnt = 0;
    for(int i = 1; i <= n; i++) {
      cur ^= (a[i] >> k) & 1;
      if(cur == 1) cnt++;
    }
    ret += cnt * (n - cnt + 1) % mod * (1LL << k) % mod;
    ret %= mod;
  }
  return ret;
}

Task 2：求和的异或

考虑和第一问一样的做法，要求的答案为异或和，考虑这个和的第 $k$ 位什么时候为 $1$ ：当出现的在这一位为 $1$ 时的区间 $[l,r]$ 内数字之和为奇数个的时候贡献为 $2^k$ 。

我们又能发现一个规律：当区间[l,r]的和的第k位是奇数时，有：

$(s[r]-s[l-1])\ mod \ 2^{k+1}\ ≥\ 2^k$
针对每一位

$k$ ，我们可以预处理出来前i项的和

$s[i]$ ，离散化这个

$s$ 以后用树状数组维护每个位置

$i$ 左右两侧是否满足上述条件。

vector<LL> bit;
int lowbit(int x) {
  return x & (-x);
}
void add(int x, LL v) {
  for(int i = x; i <= n; i+=lowbit(i)) {
    bit[i] ^= v;
  }
}
LL sum(int x) {
  LL ret = 0;
  for(int i = x; i >= 1; i-=lowbit(i)) {
    ret ^= bit[i];
  }
  return ret;
}

LL gao2() {
  vector<LL> s(n+1, 0);
  vector<LL> h(n+1, 0);
  LL ret = 0;
  for(int i = 1; i <= n; i++) {
    s[i] = s[i-1] + a[i];
  }
  auto id = [&](LL cur) {
    return lower_bound(h.begin(), h.end(), cur) - h.begin() + 1;
  };

  for(int k = 0; k < 32; k++) {
    LL tmp = 0;
    for(int i = 0; i <= n; i++) {
      h[i] = s[i] & ((1LL << (k + 1)) - 1);
    }
    sort(h.begin(), h.end());
    bit = vector<LL>(n+1, 0);
    for(int i = 0; i <= n; i++) {
      LL cur = s[i] & ((1LL << (k + 1)) - 1);
      add(id(cur), 1LL);
      tmp ^= sum(id(cur-(1LL<<k))) ^ sum(id(cur+(1LL<<k))) ^ sum(id(cur));
    }
    if(tmp == 1) ret |= (1LL << k);
  }
  return ret;
}

通过这个题，学到了要去讨论所求结果和计算过程的特点这样的思路。例如本题的两个问就是要针对区间内的异或和或答案的异或和中的每一位做讨论。

于是，遇到异或和考虑到先讨论一下每一位的贡献就对啦~

提交的时候报了CE，emmm懒得改就这样吧

#include <bits/stdc++.h>
using namespace std;
#pragma optimize("O3")

using LL = long long;
const LL mod = 998244353LL;
vector<int> a;
int n;

LL gao1() {
  LL ret = 0;
  for(int k = 0; k < 32; k++) {
    int cur = 0, cnt = 0;
    for(int i = 1; i <= n; i++) {
      cur ^= (a[i] >> k) & 1;
      if(cur == 1) cnt++;
    }
    ret += cnt * (n - cnt + 1) % mod * (1LL << k) % mod;
    ret %= mod;
  }
  return ret;
}

vector<LL> bit;
int lowbit(int x) {
  return x & (-x);
}
void add(int x, LL v) {
  for(int i = x; i <= n; i+=lowbit(i)) {
    bit[i] ^= v;
  }
}
LL sum(int x) {
  LL ret = 0;
  for(int i = x; i >= 1; i-=lowbit(i)) {
    ret ^= bit[i];
  }
  return ret;
}

LL gao2() {
  vector<LL> s(n+1, 0);
  vector<LL> h(n+1, 0);
  LL ret = 0;
  for(int i = 1; i <= n; i++) {
    s[i] = s[i-1] + a[i];
  }
  auto id = [&](LL cur) {
    return lower_bound(h.begin(), h.end(), cur) - h.begin() + 1;
  };

  for(int k = 0; k < 32; k++) {
    LL tmp = 0;
    for(int i = 0; i <= n; i++) {
      h[i] = s[i] & ((1LL << (k + 1)) - 1);
    }
    sort(h.begin(), h.end());
    bit = vector<LL>(n+1, 0);
    for(int i = 0; i <= n; i++) {
      LL cur = s[i] & ((1LL << (k + 1)) - 1);
      add(id(cur), 1LL);
      tmp ^= sum(id(cur-(1LL<<k))) ^ sum(id(cur+(1LL<<k))) ^ sum(id(cur));
    }
    if(tmp == 1) ret |= (1LL << k);
  }
  return ret;
}

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d",&n)) {
    a.resize(n+1);
    for(int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
    }
    printf("%lld %lld\n", gao1(), gao2());
  }
  return 0;
}