Submission #1131526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131526		lopkus	XORanges (eJOI19_xoranges)	C++20	100 / 100	52 ms	6216 KiB

xoranges

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2e5 + 5;

struct fenwick{
	vector<int>t;
	void build(int n) {
		t.resize(n + 1);
	}
	void update(int index,int n,int val) {
		while(index <= n) {
			t[index] ^= val;
			index += index & -index;
		}
	}
	int query(int i) {
		int ans = 0;
		while(i > 0) {
			ans ^= t[i];
			i -= i & - i;
		}
		return ans;
	}
}fenw[2];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    fenw[0].build(n);
    fenw[1].build(n);
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        fenw[i % 2].update(i, n, a[i]);
    }
    while(q--) {
        int o;
        cin >> o;
        if(o == 1) {
            int index, value;
            cin >> index >> value;
            fenw[index % 2].update(index, n, a[index]);
            a[index] = value;
            fenw[index % 2].update(index, n, a[index]);
        }
        else {
            int l, r;
            cin >> l >> r;
            int len = r - l + 1;
            if(len % 2) {
                cout << (fenw[l & 1].query(r) ^ fenw[l & 1].query(l - 1)) << "\n";
            }
            else {
                cout << 0 << "\n";
            }
        }
    }
}

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