DDOSvoid's Blog

2021牛客多校3 I Kuriyama Mirai and Exclusive Or

发表于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目描述

https://ac.nowcoder.com/acm/contest/11254/I

Solution

首先能够发现一个性质，连续数字的 $2^i$ 的这个二进制位是按照 $2^{i+1}$ 来循环的

具体的，大概是这个样子，比如说 $3,4,5,\cdots,29$ 的 $2^2$ 这位是这样的：$0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1$​​，能够看出是以 $1,1,1,1,0,0,0,0$ 循环的

我们考虑如果打差分标记的话要怎么打，能够发现是每隔 $2^i$ 打一个差分标记

那么我们对于每次操作 $0$ 可以直接打两个差分标记，对于每次操作 $1$，我们按位拆开打标记即可

需要注意对于操作 $1$，我们是打差分标记的标记，因为对于固定的二进制位，标记向后延伸的位数也是固定的，我们只需要打最开头的那个就行

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
#include <iostream>
#include <vector>
#include <cmath>
#define maxn 600010
#define maxm 30
using namespace std;

int n, m;

int d[maxn], a[maxn];

bool tag[maxn][maxm];

void update(int x, int v) {
    if (x > n) return ;
    for (int o = 0; o < 30; ++o) {
        if (v >> o & 1) d[x] ^= 1 << o;
        int k = (((v >> o) + 1) << o) - v + x;
        if (k <= n) tag[k][o] ^= 1; 
    }
}

inline void solve_1() {
    int x, y, z; cin >> x >> y >> z;
    d[x] ^= z; d[y + 1] ^= z;
}

inline void solve_2() {
    int x, y, z; cin >> x >> y >> z;
    update(x, z); update(y + 1, z + y - x + 1); 
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if (opt == 0) solve_1();
        else solve_2(); 
    }
    for (int o = 0; o < 30; ++o)
        for (int i = 1; i <= n; ++i) {
            if (i + (1 << o) <= n) tag[i + (1 << o)][o] ^= tag[i][o];
            if (tag[i][o]) d[i] ^= 1 << o;
        }
    for (int i = 1; i <= n; ++i) d[i] ^= d[i - 1], cout << (a[i] ^ d[i]) << " \n"[i == n]; 
    return 0;
}