Submission #833544

#	Time	Username	Problem	Language	Result	Execution time	Memory
833544		tolbi	XORanges (eJOI19_xoranges)	C++17	100 / 100	490 ms	10552 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
#define tol(bi) (1LL<<((long long)(bi)))
struct SegTree{
	vector<int> segtree;
	SegTree(int n){
		segtree.resize(tol(ceil(log2(n)+1))-1,0ll);
	}
	void update(int node, int val){
		node+=segtree.size()/2;
		segtree[node]=val;
		while (node){
			node=(node-1)/2;
			segtree[node]=segtree[node*2+1]^segtree[node*2+2];
		}
	}
	int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
		if (r==-1)r = segtree.size()/2;
		if (l>=tarl && r<=tarr) return segtree[node];
		if (l>tarr || r<tarl) return 0ll;
		int mid = l+(r-l)/2;
		int lnode = query(tarl, tarr, l, mid, node*2+1);
		int rnode = query(tarl, tarr, mid+1, r, node*2+2);
		return lnode^rnode;
	}
};
int main(){
	int n,q;
	cin>>n>>q;
	vector<SegTree> segtree(2,n);
	for (int i = 0; i < n; ++i)
	{
		int x;cin>>x;
		segtree[(i+1)%2].update(i,x);
	}
	while (q--){
		int ty,x,y;
		cin>>ty>>x>>y;
		if (ty==1){
			segtree[x%2].update(x-1,y);
		}
		else {
			if ((y-x)%2){
				cout<<0<<endl;
				continue;
			}
			else {
				cout<<segtree[x%2].query(x-1,y-1)<<endl;
			}
		}
	}
}

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