「Codeforces 242E」XOR on Segment

Description

给定 $n\ (1 \leq n \leq 10^5)$ 个数 $a_i\ (0 \leq a_i \leq 10^6)$，现在有 $m\ (1 \leq m \leq 5 \times 10^4)$ 个操作（操作有 $2$ 种）:

1 l r：求 $\sum\limits_{i=l}^{r}a_i\ (1 \leq l \leq r \leq n)$；

2 l r x：区间 $[l,r]\ (1 \leq l \leq r \leq n)$ 内的数对 $x\ (1 \leq x \leq 10^6)$ 异或。

Source

[Luogu]CF242E

[Codeforces]242E

Solution

前置知识：

线段树

因为是区间修改和区间查询，且异或具有结合律：$(a \oplus b) \oplus c = a \oplus (b \oplus c)$，我们很容易想到用线段树来维护。可是似乎打不了懒标记，怎么办？先考虑 $a_i$ 只有 $0$ 和 $1$ 两个值的情况，当对一条线段区间反转的时候，我们只需要让这条线段的懒标记异或 $1$，这个区间 $1$ 的个数变为 区间长度 - 原来区间 $1$ 的个数。标记下放时，如果这条线段的懒标记为 $1$，则将这条线段的左右区间反转（做上述反转操作），并清空这条线段的懒标记。

显然只有 $0$ 和 $1$ 时用线段树维护很简单，现在我们需要让这些数转化为 $0$ 和 $1$ 进行操作，这不就是把它们转化成 二进制 吗？相当于建了 $\log \max\begin{Bmatrix}a_i\end{Bmatrix}$ 棵线段树，分别维护 $a_i$ 在二进制下的每一位，以及每一位的区间和。对于即将异或的数 $x$，先找到要修改的区间 $[l,r]$，再把 $x$ 二进制拆分，如果 $x$ 在二进制下某一位是 $1$，我们就对这一位所在的线段树区间 $[l,r]$ 反转。查询时，同样先找到要查询的区间 $[l,r]$，把二进制下每一位所在的 线段树区间 $[l,r]$ 的和 × 二进制下这一位对应的值 加起来就是答案。因为每一次修改或查询都要在线段树内二进制拆分，所以时间复杂度为 $O(n\log^2n)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e5, MAX_LOG = 21;
int n, m, a[MAXN + 5];

struct SegmentTree {
    LL lazy[MAXN << 2 | 3], sum[MAX_LOG + 1][MAXN << 2 | 3];
    //sum[i][x]表示二进制下第 i 位第 x 条线段的和
    inline int lson(int x) { return x << 1; }
    inline int rson(int x) { return x << 1 | 1; }
    inline void pushUp(LL x) {
        for (int i = 0; i <= MAX_LOG; ++i)
            sum[i][x] = sum[i][lson(x)] + sum[i][rson(x)];//维护二进制下每一位
    }
    void build(int *a, int x = 1, int l = 1, int r = n) {
        if (l == r) {
            for (register int i = 0; i <= MAX_LOG; ++i)
                sum[i][x] = (a[l] >> i) & 1;//二进制拆分
            return;
        }
        int mid = (l + r) >> 1;
        build(a, lson(x), l, mid), build(a, rson(x), mid + 1, r);
        pushUp(x);
    }
    inline void modify(int x, int l, int r, LL p) {
        lazy[x] ^= p;//异或满足结合律 (a ^ b) ^ c = a ^ (b ^ c)
        for (int i = 0; i <= MAX_LOG; ++i)
            if ((p >> i) & 1)//如果第 i 位为 1
                sum[i][x] = r - l + 1 - sum[i][x];//区间内 1 的个数取反 
    }
    inline void pushDown(int x, int l, int r) {
        LL mid = (l + r) >> 1;
        modify(lson(x), l, mid, lazy[x]), modify(rson(x), mid + 1, r, lazy[x]);
        lazy[x] = 0;
    }
    void update(int ql, int qr, LL p, int l = 1, int r = n, int x = 1) {
        if (ql <= l && qr >= r) {
            modify(x, l, r, p);
            return;
        }
        if (lazy[x]) pushDown(x, l, r);
        LL mid = (l + r) >> 1;
        if (ql <= mid) update(ql, qr, p, l, mid, lson(x));
        if (qr > mid) update(ql, qr, p, mid + 1, r, rson(x));
        pushUp(x);
    }
    LL query(int ql, int qr, int l = 1, int r = n, int x = 1) {
        if (ql <= l && qr >= r) {
            LL res = 0;
            for (int i = 0; i <= MAX_LOG; ++i)
                res += sum[i][x] << i;//二进制下第 i 位对应 2 的 i 次方，累加
            return res;
        }
        if (lazy[x]) pushDown(x, l, r);
        LL res = 0, mid = (l + r) >> 1;
        if (ql <= mid) res += query(ql, qr, l, mid, lson(x));
        if (qr > mid) res += query(ql, qr, mid + 1, r, rson(x));
        return res;
    }
} tr;

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    tr.build(a);
    read(m);
    for (int i = 1; i <= m; ++i) {
        int opt, l, r;
        LL x;
        read(opt);
        if (opt == 1) {
            read(l), read(r);
            write(tr.query(l, r));
            putchar('\n');
        } else {
            read(l), read(r), read(x);
            tr.update(l, r, x);
        }
    }
    return 0;
}