Submission #748190

#	Time	Username	Problem	Language	Result	Execution time	Memory
748190		Szil	XORanges (eJOI19_xoranges)	C++14	100 / 100	103 ms	9464 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 200001;

int n, q;

struct Tree {
    vector<int> tree;

    Tree() {
        tree.resize(2*MAXN);
    }

    void upd(int u, int k) {
        u += n;
        tree[u] = k;
        for (u /= 2; u >= 1; u /= 2) {
            tree[u] = tree[2*u] ^ tree[2*u+1];
        }
    }

    int qry(int l, int r) {
        l += n; r += n;
        int res = 0;
        while (l <= r) {
            if (l % 2 == 1) res ^= tree[l++];
            if (r % 2 == 0) res ^= tree[r--];
            l /= 2; r /= 2;
        }
        return res;
    }
};

void solve(){
    cin >> n >> q;
    Tree odd, even;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        if (i & 1)
            odd.upd(i, x);
        else
            even.upd(i, x);
    }
    while (q--) {
        int type, l, r; cin >> type >> l >> r;
        if (type == 1) {
            if (l & 1)
                odd.upd(l, r);
            else
                even.upd(l, r);
        } else {
            int len = r - l + 1;
            if (len & 1) {
                if (l & 1) {
                    cout << odd.qry(l, r) << "\n";
                } else {
                    cout << even.qry(l, r) << "\n";
                }
            } else {
                cout << "0\n";
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
    return 0;
}

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