Submission #999871

#	Time	Username	Problem	Language	Result	Execution time	Memory
999871		coolboy19521	XORanges (eJOI19_xoranges)	C++17	100 / 100	98 ms	14108 KiB

xoranges

#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"

#define int long long

using namespace std;

const int sz = 2e5 + 10;

int st[2][sz * 4], a[sz];

void build(int le, int ri, int v, int x) {
    if (le == ri) {
        if (le % 2 == x) {
            st[x][v] = a[le];
        }
        return;
    }
    int mi = le + (ri - le) / 2;
    build(le, mi, v * 2, x);
    build(mi + 1, ri, v * 2 + 1, x);
    st[x][v] = st[x][v * 2] ^ st[x][v * 2 + 1];
}

void update(int le, int ri, int ix, int v, int k, int x) {
    if (le > ix || ri < ix) return;
    if (le == ix && ix == ri) {
        st[x][v] = k;
        return;
    }
    int mi = le + (ri - le) / 2;
    update(le, mi, ix, v * 2, k, x);
    update(mi + 1, ri, ix, v * 2 + 1, k, x);
    st[x][v] = st[x][v * 2] ^ st[x][v * 2 + 1];
}

int query(int le, int ri, int ql, int qr, int v, int x) {
    if (le > qr || ri < ql) return 0;
    if (ql <= le && ri <= qr) return st[x][v];
    int mi = le + (ri - le) / 2;
    int lq = query(le, mi, ql, qr, v * 2, x);
    int rq = query(mi + 1, ri, ql, qr, v * 2 + 1, x);
    return lq ^ rq;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, q;
    cin >> n >> q;

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

    build(1, n, 1, 0);
    build(1, n, 1, 1);

    while (q --) {
        int t, le, ri;
        cin >> t >> le >> ri;
        if (1 == t) {
            update(1, n, le, 1, ri, le % 2);
        } else {
            int d = ri - le + 1;
            if (d % 2) {
                cout << query(1, n, le, ri, 1, le % 2) << '\n';
            } else {
                cout << "0\n";
                // int lq = query(1, n, le, ri - d / 2, 1, (le + 1) % 2);
                // int rq = query(1, n, le + d / 2, ri, 1, (le) % 2);
                // cout << (lq ^ rq) << '\n';
            }
        }
    }
}

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