Submission #970755

#	Time	Username	Problem	Language	Result	Execution time	Memory
970755		Ludissey	XORanges (eJOI19_xoranges)	C++14	100 / 100	80 ms	9328 KiB

xoranges

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()
using namespace std;

struct FenwickTree{
    vector<int> bit;
    int n;
    FenwickTree(int vn){
        this->n=vn;
        bit.resize(vn,0);
    }
    FenwickTree(vector<int> const &a) : FenwickTree(sz(a)) {
        for (int i = 0; i < sz(a); i++) add(i, 0, a[i]);
    }
    int sum(int r){
        int ret=0;
        for (; r>=0; r=(r&(r+1))-1) ret=ret^bit[r];
        return ret;
    }
    int sum(int l, int r){
        return sum(l-1)^sum(r);
    }
    void add(int r, int prev, int delta){
        for (; r<n; r=(r|(r+1))) {
            bit[r]=bit[r]^prev;
            bit[r]=bit[r]^delta;
        }
    }
};



signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,q; cin >> n>>q;
    vector<int> uneven(n/2);
    vector<int> even((n+1)/2);
    for (int i = 0; i < n; i++)
    {
        int a; cin >> a;
        if(i%2) uneven[i/2]=a;
        else even[i/2]=a;
    }
    FenwickTree evn(even);
    FenwickTree unevn(uneven);

    for (int i = 0; i < q; i++)
    {
        int t,a,b; cin >> t >> a >> b;
        if(t==1){
            a--;
            if(a%2==0) {
                evn.add(a/2, even[a/2], b);
                even[a/2]=b;
            }
            else {
                unevn.add(a/2, uneven[a/2], b);
                uneven[a/2]=b;
            }
        }else{
            a--; b--;
            if((b-a+1)%2==0) cout << "0\n";
            else {
                if(a%2==0) cout << evn.sum(a/2, b/2) << "\n";
                else cout << unevn.sum(a/2, b/2) << "\n";
            }
        }
    }
    return 0;
}

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