Submission #815529

#	Time	Username	Problem	Language	Result	Execution time	Memory
815529		ZeroCool	XORanges (eJOI19_xoranges)	C++14	100 / 100	417 ms	11000 KiB

xoranges

#include <bits/stdc++.h>  
#define INF 1e18
#define LL long long
#define int long long
using namespace std;
	
const int mod = 1e9 + 7;
const int inf = 1e18;
const int mxn = 2e5 + 5;


template<typename T>
struct FenwickTree{
	vector<int> bit;
	int n;
	FenwickTree(int _n){
		n = _n + 69;
		bit.resize(n,0);
	}

	void update(int pos,int val){
		for(;pos<n;pos += pos & -pos)bit[pos] ^= val;
	}

	int query(int pos){
		int ans = 0;
		for(;pos;pos -= pos & -pos)ans ^= bit[pos];
		return ans;
	}

	int range(int l,int r){
		if(l == 1)return query(r);
		return query(r) ^ query(l - 1);
	}
};

     
int A[mxn];

void solve(){
	int n,q;
	cin>>n>>q;

	FenwickTree<size_t> odd(n), even(n);

	for(int i = 1;i<=n;i++)cin>>A[i];
	for(int i = 1;i<=n;i++){
		if(i % 2 == 0){
			even.update(i,A[i]);
		}else{
			odd.update(i, A[i]);
		}
	}
	

	while(q--){
		int o,a,b;
		cin>>o>>a>>b;

		if(o == 1){
			if(a % 2 == 0){
				
				even.update(a,A[a]);
				A[a] = b;
				even.update(a,A[a]);
			}
			else{
				odd.update(a,A[a]);
				A[a] = b;
				odd.update(a,A[a]);
			}
			continue;
		}
	//	cout<<a<<" "<<b<<endl;
		if((b - a + 1) % 2 == 0)cout<<0<<endl;
		else if(a % 2 == 0)cout<<even.range(a,b)<<endl;
		else cout<<odd.range(a,b)<<endl;
	}
}
     
int32_t main() {  
	#ifdef ONLINE_JUDGE
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	#endif
	solve();

	// int  n;
	// cin >>n;
	// FenwickTree fwt(n);

	// int q;
	// cin>>q;
	// while(q--){
	// 	int op;
	// 	cin>>op;

	// 	if(op == 1){
	// 		int pos,val;
	// 		cin>>pos>>val;

	// 		fwt.update(pos,val);
	// 	}else{
	// 		int pos;
	// 		cout<<fwt.query(pos)<<endl;
	// 	}
	// }
}   

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