Submission #684186

#	Time	Username	Problem	Language	Result	Execution time	Memory
684186		Tigerpants	XORanges (eJOI19_xoranges)	C++17	100 / 100	214 ms	32976 KiB

xoranges

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <string>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

#define rep(x, a, b) for (ll x = a; x < b; x++)
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()
#define sz(a) a.size()
#define resz(a, n) a.resize(n)

vll oranges;
vpll segtree;
vpll interval;

pll combine(pll x, pll y) {
    return mp(x.first ^ y.first, x.second ^ y.second);
}

pll segtree_assign(ll val, int pos) {
    if (pos & 1) {
        return mp(val, 0);
    } else {
        return mp(0, val);
    }
}

void build(int cur, int l, int r) {
    interval[cur] = mp(l, r);
    if (l == r) {
        segtree[cur] = segtree_assign(oranges[l], l);
        return;
    }
    int m = (l + r) / 2;
    build(2 * cur, l, m);
    build(2 * cur + 1, m + 1, r);
    segtree[cur] = combine(segtree[2 * cur], segtree[2 * cur + 1]);
}

pll query(int cur, int l, int r) {
    if ((interval[cur].first > r) || (interval[cur].second < l)) {
        return mp(0, 0);
    }
    if ((l <= interval[cur].first) && (interval[cur].second <= r)) {
        return segtree[cur];
    }
    return combine(query(2 * cur, l, r), query(2 * cur + 1, l, r));
}

void update(int cur, int x, ll val) {
    if ((interval[cur].first > x) || (x > interval[cur].second)) {
        return;
    }
    if (interval[cur].first == interval[cur].second) {
        segtree[cur] = segtree_assign(val, x);
        return;
    }
    update(2 * cur, x, val);
    update(2 * cur + 1, x, val);
    segtree[cur] = combine(segtree[2 * cur], segtree[2 * cur + 1]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, q;
    cin >> n >> q;

    resz(oranges, n);
    resz(segtree, 4 * n);
    resz(interval, 4 * n);
    rep(i, 0, n) {
        cin >> oranges[i];
    }
    build(1, 0, n - 1);

    /*
    rep(i, 0, 2 * n) {
        cout << "(" << segtree[i].first << ", " << segtree[i].second << ") ";
    }
    cout << endl;
    */

    ll tmpa, tmpb, tmpc;
    rep(i, 0, q) {
        cin >> tmpa >> tmpb >> tmpc;
        if (tmpa == 1) {
            update(1, tmpb - 1, tmpc);
        } else {
            if ((tmpc + tmpb) & 1) {
                cout << "0\n";
            } else {
                // odd length
                pll res = query(1, tmpb - 1, tmpc - 1);
                //cout << "(" << res.first << ", " << res.second << ")" << endl;
                if (tmpb & 1) {
                    // take even indexed, which is res.second
                    cout << res.second << "\n";
                } else {
                    cout << res.first << "\n";
                }
            }
        }
        /*
        rep(i, 0, 2 * n) {
            cout << "(" << segtree[i].first << ", " << segtree[i].second << ") ";
        }
        cout << endl;
        */
    }

    return 0;
}

// for a range: find xor of all elements, all pairs of consequtive, all triplets of consequtive, etc...
// so for x in [l, r] we want to find if this coordinate contributes or not...
// the number of ranges which include x is:
// (x - l + 1) * (r - x + 1)
// when (l - 1) + (r + 1) = r - l is odd, this number ^^ is always even so answer is 0
// when r - l is even, then x=l, l + 2, l + 4, ..., r - 2, r contribute to answer
// so we have 2 segment-trees, for even and odd

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