xor_1

Computes the sum of all consecutive subsequence sums in a given sequence.

Solution

First all prefix sums are calculated, then for all k (the number of bits in binary), the contribution at the kth bit of the binary sum of all consecutive subsequences is calculated separately, and finally the contribution of all bits is summed together to give the desired answer.

For calculating the contribution at one bit, a tree array is used. There are two tree arrays which are used to record the number of occurrences of the prefix sum for the current bit 0 or 1 and the number of occurrences of the prefix sum for the current bit 1.

Specifically, for the current position i processed to

  • If the kth bit of the binary for that position is 1, it calculates the contribution of the iso-or sum of the prefix sum to the current position by querying the tree array, while adding one to the number of occurrences of that prefix sum in bit1.
  • If the binary $k$th bit at that position is 0, it calculates the contribution of the iso-or sum of the prefix and to the current position by querying the tree array, while adding one to the number of occurrences of that prefix and in bit0.

Finally, it multiplies the contribution of each bit by the corresponding weight value 2^k and heterosyncs the contributions of all the bits together as the final answer.

Code

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
#include <iostream>
#define ll long long
using namespace std;
const int MAX_N = 1e5 + 10;
int n;
int prefix_sum[MAX_N];
int lim;
struct BinaryIndexedTree {
    ll bit[MAX_N << 4];
    inline void update(int x, ll t) {
        x += 1;
        for (; x <= lim + 1; x += x & (-x))
            bit[x] += t;
    }
    inline ll query(int x) {
        x += 1;
        ll ans = 0;
        for (; x > 0; x -= x & (-x)) {
            ans += bit[x];
        }
        return ans;
    }
    inline ll get_sum(int l, int r) {
        return query(r) - query(l);
    }
    inline void clear() {
        for (int i = 0; i <= lim + 1; i++)
            bit[i] = 0;
    }
} BIT_0, BIT_1;
ll ans;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> prefix_sum[i];
        prefix_sum[i] += prefix_sum[i - 1];
    }
    for (int k = 0; (1 << k) <= prefix_sum[n]; k++) {
        lim = (1 << k) - 1;
        ll res = 0;
        for (int i = 0; i <= n; i++) {
            int check = (prefix_sum[i] >> k) & 1;
            int lst = prefix_sum[i] & lim;
            if (check) {//1
                res += BIT_0.get_sum(-1, lst) + BIT_1.get_sum(lst, lim);
                BIT_1.update(lst, 1);
            } else {// 0
                res += BIT_1.get_sum(-1, lst) + BIT_0.get_sum(lst,lim);
                BIT_0.update(lst,1);
            }
        }
        ans += (1 << k) * (res % 2);
        BIT_1.clear();
        BIT_0.clear();
    }
    cout << ans;
    return 0;
}

xor_2

Problem

There is a sequence of integers of length n.
We can divide this sequence into m consecutive intervals arbitrarily, and let the xor sum of the numbers in each interval be eie_i,
Find the smallest value of e1e_1 or e2e_2 or e3e_3 or ⋯em\cdots e_{m}

Solution

For each bit i, count the number of intervals whose XOR sum has a 0 bit in position i using an array vis, which is initialized to 0.
If there are at least m such intervals, mark the positions of the array a that have a 1 bit in position i as visited by setting the corresponding values in vis to 1.
Otherwise, set the i-th bit in the answer variable ans to 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
#include <iostream>
#define ll long long
using namespace std;
const int MAX_N = 500010;
ll arr[MAX_N];
int visited[MAX_N];
int n, m;
ll ans;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        arr[i] ^= arr[i - 1]; // compute XOR prefix sum
    }

    // iterate over all bits from the most significant to the least significant
    for (int bit_pos = 60; bit_pos >= 0; bit_pos--) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            // count number of intervals whose XOR sum has a 0 bit in position bit_pos
            if (!visited[i] && (arr[i] & (1ll << bit_pos)) == 0) {
                cnt++;
            }
        }

        if ((arr[n] & (1ll << bit_pos)) == 0 && cnt >= m) {
            // mark positions of array arr that have a 1 bit in position bit_pos as visited
            for (int i = 1; i <= n; i++) {
                if (arr[i] & (1ll << bit_pos)) {
                    visited[i] = 1;
                }
            }
        } else {
            // set the i-th bit in the answer variable ans to 1
            ans |= (1ll << bit_pos);
        }
    }
    cout << ans << "\n";
    return 0;
}