Submission #1219499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219499		Aisha	XORanges (eJOI19_xoranges)	C++20	0 / 100	50 ms	13128 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct node {
    int j;
    int t;

    node() {
        j = -1;
        t = -1;
    }
};

node merge(node a, node b) {
    node c;
    if (a.t == -1 && b.t == -1) c.t = -1;
    else if (a.t == -1) c.t = b.t;
    else if (b.t == -1) c.t = a.t;
    else c.t = a.t ^ b.t;

    if (a.j == -1 && b.j == -1) c.j = -1;
    else if (a.j == -1) c.j = b.j;
    else if (b.j == -1) c.j = a.j;
    else c.j = a.j ^ b.j; 
    
    return c;
}

struct SegTree {
    int N = 1;
    vector <node> t;
    vector <int> a;

    void init(vector <int> b) {
        int n = b.size();
        while (N < n) N *= 2;
        t.assign(2 * N, node());

        a = b;
    }

    void build(int i, int tl, int tr) {
        if (tl == tr) {
            if (tl % 2) t[i].t = a[tl];
            else t[i].j = a[tl];
            return;
        }

        int tm = (tl + tr) >> 1;
        build(i << 1, tl, tm);
        build(i << 1 | 1, tm + 1, tr);

        t[i] = merge(t[i << 1], t[i << 1 | 1]);
    }

    void update(int i, int tl, int tr, int ind, int x) {
        if (tl == tr) {
            if (tl % 2) t[i].t = x;
            else t[i].j = x;
            return;
        }

        int tm = (tl + tr) >> 1;
        if (ind <= tm) update(i << 1, tl, tm, ind, x);
        else update(i << 1 | 1, tm + 1, tr, ind, x);

        t[i] = merge(t[i << 1], t[i << 1 | 1]);
    }

    node get(int i, int tl, int tr, int l, int r) {
        if (l > tr || r < tl) return node();
        if (tl == l && tr == r) return t[i];

        int tm = (tl + tr) >> 1;
        if (r <= tm) return get(i << 1, tl, tm, l, r);
        if (l > tm) return get(i << 1 | 1, tm + 1, tr, l, r);

        return merge(get(i << 1, tl, tm, l, tm), get(i << 1 | 1, tm + 1, tr, tm + 1, r));
    }
};

signed main() {
    int n, q;
    cin >> n >> q;

    vector <int> a(n + 1);
    for (int i = 1; i <= n; i ++) cin >> a[i];

    SegTree t;
    t.init(a);
    t.build(1, 1, n);

    while (q --) {
        int op;
        cin >> op;

        if (op == 1) {
            int i, x;
            cin >> i >> x;

            t.update(1, 1, n, i, x);
        } else {
            int l, r;
            cin >> l >> r;
        
            if ((r - l + 1) % 2 == 0) {
                cout << 0 << endl;
                return 0;
            }

            node ans = t.get(1, 1, n, l, r);
            if (r % 2) cout << ans.t << endl;
            else cout << ans.j << endl;
        }
    }

    return 0;
}

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