Submission #1285494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285494		thuhienne	XORanges (eJOI19_xoranges)	C++20	100 / 100	64 ms	6104 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct FenwickXor {
    int n;
    vector<ll> bit;
    FenwickXor(int n=0){ init(n); }
    void init(int _n){
        n = _n;
        bit.assign(n+1, 0);
    }
    // apply xor with val at position idx
    void update(int idx, ll val){
        for(; idx <= n; idx += idx & -idx) bit[idx] ^= val;
    }
    // prefix xor [1..idx]
    ll query(int idx){
        ll res = 0;
        for(; idx > 0; idx -= idx & -idx) res ^= bit[idx];
        return res;
    }
    // range xor [l..r]
    ll range_query(int l, int r){
        if(l>r) return 0;
        return query(r) ^ query(l-1);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if(!(cin >> n >> m)) return 0;
    vector<ll> a(n+1);
    for(int i=1;i<=n;i++) cin >> a[i];

    FenwickXor bitOdd(n), bitEven(n);
    // parity: i%2==1 -> odd, i%2==0 -> even
    for(int i=1;i<=n;i++){
        if(i%2==1) bitOdd.update(i, a[i]);
        else bitEven.update(i, a[i]);
    }

    while(m--){
        int type; cin >> type;
        if(type == 1){
            int idx; ll val; cin >> idx >> val;
            ll delta = a[idx] ^ val; // value to xor into Fenwick
            if(delta != 0){
                if(idx % 2 == 1) bitOdd.update(idx, delta);
                else bitEven.update(idx, delta);
                a[idx] = val;
            } else {
                a[idx] = val; // vẫn cập nhật mảng (mặc dù không thay đổi tree)
            }
        } else if(type == 2){
            int l, r; cin >> l >> r;
            if( (l % 2) != (r % 2) ){
                cout << 0 << '\n';
            } else {
                if(l % 2 == 1){
                    cout << bitOdd.range_query(l, r) << '\n';
                } else {
                    cout << bitEven.range_query(l, r) << '\n';
                }
            }
        }
    }

    return 0;
}

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