Submission #896803

#	Time	Username	Problem	Language	Result	Execution time	Memory
896803		Jawad_Akbar_JJ	XORanges (eJOI19_xoranges)	C++17	100 / 100	454 ms	12800 KiB

xoranges

#include <iostream>
#include <vector>


using namespace std;
const int N = (1<<18) + 1;

struct node{
	int xr = 0;
} sg[N<<2][2];

void insert(int i,int v,int cur = 1,int st = 1,int en = N){
	if (i>=en or i<st)
		return;
	// cout<<st<<" "<<en<<endl;
	sg[cur][i%2].xr ^= v;
	if (en - st == 1)
		return;

	int lc = cur + cur,rc = lc + 1,mid = (st + en)/2;

	insert(i,v,lc,st,mid);
	insert(i,v,rc,mid,en);
}

int get(int l,int r,int t,int cur = 1,int st = 1,int en = N){
	if (l>=en or r<=st)
		return 0;

	if (l<=st and r>=en)
		return sg[cur][t].xr;

	int lc = cur + cur,rc = lc + 1,mid = (st + en)/2;

	return get(l,r,t,lc,st,mid) ^ get(l,r,t,rc,mid,en);
}
int arr[N];
int main(){
	// insert(1,2);
	int n,m;
	cin>>n>>m;

	for (int i=1;i<=n;i++){
		int a;
		cin>>a;
		arr[i] = a;
		insert(i,a);
	}

	while (m--){
		int t;
		cin>>t;

		if (t==1){
			int i,a;
			cin>>i>>a;
			insert(i,arr[i]);
			insert(i,a);
			arr[i] = a;
		}
		else{
			int l,r;
			cin>>l>>r;

			if ((r - l + 1)%2==0)
				cout<<0<<'\n';
			else
				cout<<get(l,r+1,l%2)<<'\n';
		}
	}
}

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