CodeForces 242E XOR on Segment 【线段树】【异或】

发表于 | 更新于 | 分类于

题目大意：

给出一个包含n个数的数组，先要对数组中的数进行m次操作，当输入的指令为1时，输出区间l~r的数的和；当输入的指令为2时，将区间l~r的数全部^x。

解题思路：

区间更新，区间求和，线段树的典型应用。求和好解决，但是更新呢？如果单点更新肯定超时不用想。
考虑异或的性质，是否可以将存的数分解为二进制的形式进行存储呢，答案是可以的。因为$a_i$最大不超过$ 2^{20} $，所以将sum改为大小为20的数组来存取二进制形式的每一位是能实现的。更新时还是延迟标记的思想，查询时再将这些数“合起来”就行了。

Mycode：

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = 100010;

int a[MAX];
struct node
{
    int l, r;
    int sum[22], lazy;
} tree[MAX<<2];
void pushup(int rt)
{
    for(int i = 0; i <= 20; ++i)
        tree[rt].sum[i] = tree[rt<<1].sum[i] + tree[rt<<1|1].sum[i];
}

void pushdown(int rt)
{
    int mid = tree[rt].r + tree[rt].l >> 1;
    for(int i = 0; i <= 20; ++i)
    {
        if(tree[rt].lazy & (1 << i))
        {
            tree[rt<<1].sum[i] = mid - tree[rt].l + 1 - tree[rt<<1].sum[i];
            tree[rt<<1|1].sum[i] = tree[rt].r - mid - tree[rt<<1|1].sum[i];
        }
    }

    tree[rt<<1].lazy ^= tree[rt].lazy;
    tree[rt<<1|1].lazy ^= tree[rt].lazy;
    tree[rt].lazy = 0;
}

void build(int l, int r, int rt)
{
    tree[rt].l = l;
    tree[rt].r = r;
    tree[rt].lazy = 0;
    if(l == r)
    {
        for(int i = 0; i <= 20; ++i)
            tree[rt].sum[i] = (a[l] & (1 << i)) > 0;
        return ;
    }
    int mid = l + r >> 1;
    build(l, mid, rt<<1);
    build(mid+1, r, rt<<1|1);
    pushup(rt);
}

void update(int l, int r, int val, int rt)
{
    if(tree[rt].l == l && tree[rt].r == r)
    {
        tree[rt].lazy ^= val;
        for(int i = 0; i <= 20; ++i)
        {
            //注意这里的更新值
            if(val & (1 << i))
                tree[rt].sum[i] = r - l + 1 - tree[rt].sum[i];
        }
        return ;
    }
    if(tree[rt].lazy)
        pushdown(rt);
    int mid = (tree[rt].l + tree[rt].r) >> 1;
    if(r <= mid)
        update(l, r, val, rt<<1);
    else if(l > mid)
        update(l, r, val, rt<<1|1);
    else
    {
        update(l, mid, val, rt<<1);
        update(mid+1, r, val, rt<<1|1);
    }
    pushup(rt);
}

long long query(int l, int r, int rt)
{
    long long res = 0;
    if(tree[rt].l == l && tree[rt].r == r)
    {
        for(int i = 0; i <= 20; ++i)
            res += (1ll << i) * tree[rt].sum[i];
        return res;
    }
    if(tree[rt].lazy)
        pushdown(rt);
    int mid = (tree[rt].l + tree[rt].r) >> 1;
    if(r <= mid)
        res += query(l, r, rt<<1);
    else if(l > mid)
        res += query(l, r, rt<<1|1);
    else
        res += query(l, mid, rt<<1) + query(mid+1, r, rt<<1|1);
    return res;
}

int main()
{
    int n, m, l, r, val, Q;
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i)
        scanf("%d",&a[i]);
    build(1, n, 1);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d%d",&Q,&l,&r);
        if(Q == 1)
            printf("%lld\n", query(l, r, 1));
        else
        {
            scanf("%d", &val);
            update(l, r, val, 1);
        }
    }
    return 0;
}
Donate comment here
0%