Submission #1235346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235346		GoBananas69	XORanges (eJOI19_xoranges)	C++20	0 / 100	64 ms	7352 KiB

xoranges

#include <algorithm>
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;

struct SegmentTree {
  private:
    vector<int> nums, tree;
    int n;
    void build(int i, int L, int R) {
        if (L == R) {
            tree[i] = nums[L];
            return;
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        build(x, L, m);
        build(y, m + 1, R);
        tree[i] = tree[x] ^ tree[y];
    }
    void update(int i, int L, int R, int p, int v) {
        if (L == R) {
            tree[i] = v;
            return;
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        if (p <= m) {
            update(x, L, m, p, v);
        } else {
            update(y, m + 1, R, p, v);
        }
        tree[i] = tree[x] ^ tree[y];
    }
    int query(int i, int L, int R, int l, int r) {
        if (L == l && r == R) {
            return tree[i];
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        if (r <= m) {
            return query(x, L, m, l, r);
        } else if (l > m) {
            return query(y, m + 1, r, l, r);
        } else {
            int q1 = query(x, L, m, l, m);
            int q2 = query(y, m + 1, R, m + 1, r);
            return q1 ^ q2;
        }
    }

  public:
    SegmentTree(vector<int> &v) : nums(v), n(nums.size()) {
        tree.assign(4 * n, 0);
        build(0, 0, n - 1);
    }
    void update(int p, int v) { update(0, 0, n - 1, p, v); }
    int query(int l, int r) { return query(0, 0, n - 1, l, r); }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    vector<int> nums(n);
    for (int &i : nums) cin >> i;
    vector<int> o, e;
    for (int i = 0; i < n; ++i) {
        if (i & 1) o.push_back(nums[i]);
        else e.push_back(nums[i]);
    }
    SegmentTree odd(o);
    SegmentTree even(e);
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int p, v;
            cin >> p >> v;
            --p;
            if (p & 1) {
                odd.update(p / 2, v);
            } else {
                even.update(p / 2, v);
            }
        } else if (type == 2) {
            int l, r;
            cin >> l >> r;
            --l;
            --r;
            if (!((r - l + 1) & 1)) {
                cout << "0\n";
                continue;
            }
            if (l & 1) {
                cout << odd.query(l / 2, r / 2) << '\n';
            } else {
                cout << even.query(l / 2, r / 2) << '\n';
            }
        }
    }
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 25
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25