CodeForces 242E XOR on Segment

十一月 03, 2020 4258

题意简述

给定一个序列，要求支持两种操作：

  1. 询问区间和
  2. 将某一个区间的数异或上一个值

解题思路

一个挺妙的思路。需要信息支持逐位维护。

考虑把序列的每个数拆位，拆成一个矩阵，其中元素 d_{i, j} 表示第 i 个数的第 j 个二进制位是 0 还是 1，然后接下来操作都是对每一位进行维护。

区间和肯定是可以逐位维护的，实际上是每一位乘上权值然后加和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
比如序列 1 2 3 6，拆成 4 位二进制就是：
1 2 3 6
↓ ↓ ↓ ↓
1 0 1 0 → = 2
0 1 1 1   = 3
0 0 0 1   = 1
0 0 0 0   = 0
求这个序列的和就等于
2 * (1 << 0) 
+ 3 * (1 << 1) 
+ 1 * (1 << 2)
+ 0 * (1 << 3)
= 12
= 1 + 2 + 3 + 6

区间异或不用说，肯定可以逐位维护。相当于，如果要异或的数某一位是 1，那就把表示那一位的整一行取反。

1
2
3
4
5
比如序列 1 2 3 6，现在要把它异或上 4
1 0 1 0 ^ 0 = 1 0 1 0
0 1 1 1 ^ 0 = 0 1 1 1
0 0 0 1 ^ 1 = 1 1 1 0
0 0 0 0 ^ 0 = 0 0 0 0

所以我们可以这样解决：维护 20 个 01 线段树，每一个线段树表示拆出来的一位，要求支持区间取反，区间求和。

时间复杂度 \mathcal{O}(20 \times q \log n)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;
#define forall(G,u) for (int i_ = 0, __for_siz__ = (int) G[u].size(); i_ < __for_siz__; ++i_) 

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 1e5 + 10;

int n, m, aa[MAXN];

struct SegmentTree {
    long long int sum[MAXN << 2], tag[MAXN << 2];

    #define lson ((p) << 1)
    #define rson ((p) << 1 | 1)

    void Update(int p) { sum[p] = sum[lson] + sum[rson]; }
    void buildTree(int p, int l, int r, long long int bit) {
        if (l == r) {
            sum[p] = (aa[l] >> bit) & 1;
            return;
        } int mid = (l + r) >> 1;
        buildTree(lson, l, mid, bit);
        buildTree(rson, mid + 1,r , bit);
        Update(p);
    }
    void Inverse(int p, int l, int r) {
        sum[p] = r - l + 1 - sum[p];
        tag[p] ^= 1;
    }
    void Pushdown(int p, int l, int r) {
        if (tag[p]) {
            int mid = (l + r) >> 1;
            Inverse(lson, l, mid);
            Inverse(rson, mid + 1, r);
            tag[p] = 0;
        }
    }
    void Modify(int p, int l, int r, int ll, int rr) {
        if (l == ll && rr == r) {
            Inverse(p, l, r); return;
        } int mid = (l + r) >> 1;
        Pushdown(p, l, r);
        if (rr <= mid) Modify(lson, l, mid, ll, rr);
        else if (mid + 1 <= ll) Modify(rson, mid + 1, r, ll, rr);
        else {
            Modify(lson, l, mid, ll, mid);
            Modify(rson, mid + 1, r, mid + 1, rr);
        } Update(p);
    }
    long long int Query(int p, int l, int r, int ll, int rr, long long int bit) {
        if (l == ll && rr == r) {
            return sum[p] * (1 << bit);
        } int mid = (l + r) >> 1;
        Pushdown(p, l, r);
        if (rr <= mid) return Query(lson, l, mid, ll, rr, bit);
        else if (mid + 1 <= ll) return Query(rson, mid + 1, r, ll, rr, bit);
        else return Query(lson, l, mid, ll, mid, bit) + Query(rson, mid + 1, r, mid + 1, rr, bit);
    }
} bits[20];

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) aa[i] = read();
    for (int bt = 0; bt <= 19; ++bt) bits[bt].buildTree(1, 1, n, bt);
    m = read();
    for (int i = 1; i <= m; ++i) {
        int t = read(); int l = read(); int r = read();
        if (t == 1) {
            long long int ans = 0;
            for (int bt = 0; bt <= 19; ++bt)
                ans += bits[bt].Query(1, 1, n, l, r, bt);
            printf("%lld\n", ans);
        } else {
            int x = read();
            for (int bt = 0; bt <= 19; ++bt) {
                if ((x >> bt) & 1) bits[bt].Modify(1, 1, n, l, r);
            }
        }
    }
    return 0;
}