제출 #857203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857203		DP_196	XORanges (eJOI19_xoranges)	C++14	100 / 100	83 ms	11152 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

#define int int64_t
#define sz(x) (int)x.size()
#define MASK(i) ((1LL) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & (1LL))
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b, 1) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b, 1) : 0); }

const int MAXN = 2e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, q, a[MAXN];

struct FenwickTree {
    int n;
    vector<int> bit;

    FenwickTree (int _n) {
        n = _n;
        bit.assign(n + 7, 0);
    }

    void update (int i, int x) {
        for (; i <= n; i += i & -i) bit[i] ^= x;
    }

    int get(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i) res ^= bit[i];
        return res;
    }
};

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

    FenwickTree itEven(n), itOdd(n);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i & 1) itOdd.update(i, a[i]);
        else itEven.update(i, a[i]);
    }

    while (q--) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t == 1) {
            if (u & 1) itOdd.update(u, a[u]);
            else itEven.update(u, a[u]);

            a[u] = v;

            if (u & 1) itOdd.update(u, a[u]);
            else itEven.update(u, a[u]);
        }
        else {
            if ((v - u + 1) % 2 == 0) cout << 0 << '\n';
            else {
                if (u & 1) cout << (itOdd.get(v) ^ itOdd.get(u - 1)) << '\n';
                else  cout << (itEven.get(v) ^ itEven.get(u - 1)) << '\n';
            }
        }
    }
}

#define TASK ""
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    int ntest = 1;
    //cin >> ntest;
    while (ntest--) solve();

    return 0;
}
//612

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