Submission #369882

#	Time	Username	Problem	Language	Result	Execution time	Memory
369882		AdamGS	XORanges (eJOI19_xoranges)	C++14	100 / 100	120 ms	12164 KiB

xoranges

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
const ll LIM=2e5+7;
ll T[3*LIM][2], N=1;
ll cnt(ll l, ll r, ll k) {
    l+=N; r+=N;
    ll ans=T[l][k];
    if(l!=r) ans^=T[r][k];
    while(l/2!=r/2) {
        if(l%2==0) ans^=T[l+1][k];
        if(r%2==1) ans^=T[r-1][k];
        l/=2; r/=2;
    }
    return ans;
}
void upd(ll v, ll x, ll k) {
    v+=N;
    while(v) {
        T[v][k]^=x;
        v/=2;
    }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q;
    cin >> n >> q;
    while(N<n) N*=2;
    rep(i, n) cin >> T[N+i/2][i%2];
    for(ll i=N-1; i; --i) {
        T[i][0]=T[2*i][0]^T[2*i+1][0];
        T[i][1]=T[2*i][1]^T[2*i+1][1];
    }
    while(q--) {
        ll x, a, b;
        cin >> x >> a >> b; --a;
        if(x==1) {
            upd(a/2, T[N+a/2][a%2]^b, a%2);
        } else {
            --b;
            if((b-a)%2==1) {
                cout << "0\n";
            } else {
                cout << cnt(a/2, b/2, a%2) << '\n';
            }
        }
    }
}

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