Submission #1236088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236088		GoBananas69	XORanges (eJOI19_xoranges)	C++20	0 / 100	73 ms	21828 KiB

xoranges

#include <algorithm>
#include <iostream>
#include <vector>
// #include "outputdebug.cpp"
typedef long long ll;
using namespace std;

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

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

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

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