JZOJ 5063 异或与区间加

其实我也不知道这个题算分块还是莫队。

起手式是做 si=⨁ij=1aj，然后对答案数组来一个反向差分（为了方便），则问题变为对于 [l,r] 内满足 si⊕sj=k (i<j) 的数对操作 bi←bi+w,bj←bj−w。
好，我们知道有一个题是查询区间内上述数对的个数。那么我们不妨沿用原来的做法，即莫队。则其中一个端点的操作可以现场完成，并对另一个端点会转化出 O(n√m) 个四参数的操作 (l,r,x,w) 表示将 [l,r] 内 si=x 的 i 作 si←si+w。
当然，因为莫队本身只刻画不同询问间的位移，所以为了能计算答案我们要把所有 w 后缀和。

自然将不同的 si 划分开，在其中再次差分，则问题变为一些 lower_bound 查询。
带 log 肯定是不好的。一个做法是离线，但是那样难免会花费同复杂度的空间，不太划算。事实上莫队本身就在做若干次 O(1) 位移，这意味着当前的左右端点在任一 si 的等价类中的 lower_bound 都可以同时维护，因为每个位置只从属于一个等价类。

过了几天想了一下，其实还有另一个比较好写的做法。注意到莫队本身就是左右端点一直位移的过程，那么假设我们能将莫队整个扫描过程逆序，那其实就能将对应的修改直接在之后的反向扫描中下放到对应位置上。
其实这是通过转置原理得出的（
常数相当小。在老年 OJ 上仍然能跑出 240ms 的好成绩。

代码：

#include <cmath>
#include <cstdio>
#include <algorithm>
#include <unordered_map>

using uint = unsigned int;

using namespace std;

const int N = 1.5e5;

int n, m, k;

int s[N + 5], sId[N + 5], sXorK[N + 5], tot;
unordered_map<int, int> id;

int block, pos[N + 5];

struct operation {
  int l, r;
  uint w;
  inline bool operator<(const operation &o) const {
    return pos[l] != pos[o.l] ? pos[l] < pos[o.l] : pos[l] & 1 ? r < o.r : r > o.r;
  }
} opt[N + 5];

int cnt[N + 5];
uint sum[N + 5], ans[N + 5];

int main() {
  freopen("xor.in", "r", stdin), freopen("xor.out", "w", stdout);
  scanf("%d%d%d", &n, &m, &k), block = min<int>(n / sqrt(m) + 1, n);
  sId[0] = id[0] = ++tot;
  for (int i = 1; i <= n; ++i)
    scanf("%d", s + i), s[i] ^= s[i - 1], pos[i] = (i - 1) / block + 1,
    sId[i] = id.count(s[i]) ? id[s[i]] : (id[s[i]] = ++tot);
  for (int i = 0; i <= n; ++i)
    if (id.count(s[i] ^ k))
      sXorK[i] = id[s[i] ^ k];
  for (int i = 1; i <= m; ++i)
    scanf("%d%d%u", &opt[i].l, &opt[i].r, &opt[i].w);
  sort(opt + 1, opt + m + 1), opt[0].l = 1;
  for (int i = m - 1; i; --i)
    opt[i].w += opt[i + 1].w;
  int l = 1, r = 0;
  ++cnt[sId[0]];
  for (int i = 1; i <= m; ++i) {
    while (r < opt[i].r)
      ++r, ans[r] += opt[i].w * cnt[sXorK[r]], ++cnt[sId[r]];
    while (r > opt[i].r)
      --cnt[sId[r]], ans[r] -= opt[i].w * cnt[sXorK[r]], --r;
    while (l < opt[i].l)
      --cnt[sId[l - 1]], ans[l - 1] += opt[i].w * cnt[sXorK[l - 1]], ++l;
    while (l > opt[i].l)
      --l, ans[l - 1] -= opt[i].w * cnt[sXorK[l - 1]], ++cnt[sId[l - 1]];
  }
  for (int i = m; i; --i) {
    while (l < opt[i - 1].l)
      ans[l - 1] += sum[sId[l - 1]], sum[sXorK[l - 1]] += opt[i].w, ++l;
    while (l > opt[i - 1].l)
      --l, sum[sXorK[l - 1]] -= opt[i].w, ans[l - 1] -= sum[sId[l - 1]];
    while (r < opt[i - 1].r)
      ++r, sum[sXorK[r]] += opt[i].w, ans[r] -= sum[sId[r]];
    while (r > opt[i - 1].r)
      ans[r] += sum[sId[r]], sum[sXorK[r]] -= opt[i].w, --r;
  }
  for (int i = n - 1; i; --i)
    ans[i] += ans[i + 1];
  for (int i = 1; i <= n; ++i)
    printf("%u%c", ans[i] & ((1U << 30) - 1), " \n"[i == n]);
}