Submission #810767

#	Time	Username	Problem	Language	Result	Execution time	Memory
810767		Acanikolic	XORanges (eJOI19_xoranges)	C++14	0 / 100	81 ms	11736 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(l == r) {
    			cout << a[l] << '\n';
    			continue;
    		}
    		/*for(int i=1;i<=n;i++) cout << get(i) << ' ';
    		cout << endl;
    		cout << get(r) << ' ' << get(l-1) << endl;*/
    		cout << (ft[(r-l+1) & 1].get(r) ^ ft[(r-l+1) & 1].get(l-1)) << '\n';
    	}
    }
}

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