Submission #981627

#	Time	Username	Problem	Language	Result	Execution time	Memory
981627		DP_196	XORanges (eJOI19_xoranges)	C++14	100 / 100	117 ms	19628 KiB

xoranges

#include <bits/stdc++.h>

#ifdef OP_DEBUG
    #include <algo/debug.h>
#else
    #define debug(...) 26
#endif

using namespace std;

#define int 	long long
#define sz(v)   (int)(v).size()
#define all(v)  (v).begin(), (v).end()
#define TcT     template <class T

const   int     MOD = (int)1e9 + 7, INF = (int)4e18 + 18;

TcT>            bool minimize(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }
TcT>            bool maximize(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }

void solve();

int32_t main() {
    cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
    int testcases = 1;

#define TC 0
    if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
}

/* [Pham Hung Anh - 11I - Tran Hung Dao High School for Gifted Student] */

const int N = 2e5 + 5;

int n, q;
int a[N];
int pref[N][2];

struct SegmentTree {
    int node[4 * N + 7][2];

    void build(int type, int id = 1, int left = 1, int right = n) {
        if (left == right)
            return void(node[id][type] = pref[left][type]);
        
        int mid = (left + right) >> 1;
        build(type, id << 1, left, mid);
        build(type, id << 1 | 1, mid + 1, right);

        node[id][type] = node[id << 1][type] ^  node[id << 1 | 1][type];
    }

    void update(int type, int pos, int val, int id = 1, int left = 1, int right = n) {
        if (pos < left || right < pos)
            return;
        
        if (left == right) {
            node[id][type] ^= a[pos];
            a[pos] = val;
            node[id][type] ^= a[pos];
            return;
        }

        int mid = (left + right) >> 1;
        update(type, pos, val, id << 1, left, mid);
        update(type, pos, val, id << 1 | 1, mid + 1, right);

        node[id][type] = node[id << 1][type] ^ node[id << 1 | 1][type];
    }

    int get(int type, int l, int r, int id = 1, int left = 1, int right = n) {
        if (r < left || right < l)
            return 0;
        
        if (l <= left && right <= r)
            return node[id][type];
        
        int mid = (left + right) >> 1;
        int lc = get(type, l, r, id << 1, left, mid);
        int rc = get(type, l, r, id << 1 | 1, mid + 1, right);

        return (lc ^ rc);
    }
} st;

void solve() {
    cin >> n >> q;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    
    for (int i = 1; i <= n; ++i) {
        pref[i][0] = pref[i - 1][0] ^ ((i & 1) ? 0 : a[i]);
        pref[i][1] = pref[i - 1][1] ^ ((i & 1) ? a[i] : 0);
    }

    st.build(0);
    st.build(1);

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

        if (op == 1) {
            int u, v; cin >> u >> v;

            st.update(u & 1, u, v);
        } else {
            int l, r; cin >> l >> r;

            if ((r - l + 1) % 2 == 0)
                cout << 0 << '\n';
            else
                cout << st.get(l & 1, l - 1, r) << '\n';
        }
    }
}

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