Submission #1131671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131671		qrn	XORanges (eJOI19_xoranges)	C++20	100 / 100	110 ms	28532 KiB

xoranges

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ins insert
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long 

const intt mod = 1e9 + 7;
const intt base = 31;
const intt inf = 1e18;
const intt mxN = 3e5 + 10;

vector<vector<intt>> seg(2, vector<intt>(4 * mxN, 0ll));
intt a[mxN];

void build(intt node, intt l, intt r) {
    if(l == r) {
        seg[l & 1][node] = a[l];
        return;
    }
    intt mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    seg[0][node] = seg[0][node * 2] ^ seg[0][node * 2 + 1];
    seg[1][node] = seg[1][node * 2] ^ seg[1][node * 2 + 1];
}

void update(intt node, intt l, intt r, intt pos, intt val) {
    // cout << l << " " << r << endl;
    if(l == r) {
        seg[l & 1][node] = val;
        return;
    }
    intt mid = (l + r) / 2;
    if(pos <= mid) {
        update(node * 2, l, mid, pos, val);
    } else {
        update(node * 2 + 1, mid + 1, r, pos, val);
    }
    seg[0][node] = seg[0][node * 2] ^ seg[0][node * 2 + 1];
    seg[1][node] = seg[1][node * 2] ^ seg[1][node * 2 + 1];
}

intt get(intt node, intt l, intt r, intt ql, intt qr, intt init_l) {
    if(qr < l || ql > r) return 0;
    if(ql <= l && r <= qr){
        return seg[init_l & 1][node];
    }
    
    intt mid = (l + r) / 2;
    intt gg = get(node * 2, l, mid, ql, qr, init_l);
    intt ggg = get(node * 2 + 1, mid + 1, r, ql, qr, init_l);
    return gg ^ ggg;
}

void solve() {
    intt n, q;
    cin >> n >> q;
    for(intt i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    build(1, 1, n);
    
    while(q--) {
        intt t, a, b;
        cin >> t >> a >> b;
        if(t == 1ll) {
            update(1, 1, n, a, b);
        } else {
            if(((b - a + 1) & 1) == 0) {
                cout << 0 << endl;
                continue;
            }
            cout << get(1, 1, n, a, b, a&1) << endl;
        }
    }
}

signed main() {
    SPEED;

    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

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