Submission #810829

#	Time	Username	Problem	Language	Result	Execution time	Memory
810829		Acanikolic	XORanges (eJOI19_xoranges)	C++14	100 / 100	82 ms	10996 KiB

xoranges

#include <bits/stdc++.h>
			 		
#define int long long 
			 
#define pb push_back 
			
#define F first
			 
#define S second
			 
using namespace std;
			 
const int N = 2e5+10;
			 
const int mod = 1e9+7;
			 
const int inf = 1e18;
 
int a[N];
 
struct fenwick {
	vector<int>fenw;
	void build(int n) {
		fenw.resize(n+1);
	}
	void update(int index,int n,int val) {
		while(index <= n) {
			fenw[index] ^= val;
			index += index & -index;
		}
	}
	int get(int x) {
		int ret = 0;
		while(x >= 1) {
			ret ^= fenw[x];
			x -= x & -x;
		}
		return ret;
	}
};
		
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
	 
    int n,Q;
    cin >> n >> Q;
    fenwick ft[2];
    ft[0].build(n);
    ft[1].build(n);
    for(int i=1;i<=n;i++) {
    	cin >> a[i];
    	ft[i & 1].update(i,n,a[i]);
    }
    //cout << ft[1].get(n) << ' ' << ft[0].get(n) << endl;
    while(Q--) {
    	int type;
    	cin >> type;
    	if(type & 1) {
    		int index,val;
    		cin >> index >> val;
    		ft[index & 1].update(index,n,a[index]);
    		a[index] = val;
    		ft[index & 1].update(index,n,a[index]);
    	}
    	else {
    		int l,r;
    		cin >> l >> r;
    		if((r-l+1) % 2 == 0) {
    			cout << 0 << '\n';
    			continue;
    		}
    		cout << (ft[l & 1].get(r) ^ ft[l & 1].get(l-1)) << '\n';
    	}
    }
}

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