Submission #446799

#	Time	Username	Problem	Language	Result	Execution time	Memory
446799		osmanallazov	XORanges (eJOI19_xoranges)	C++14	100 / 100	734 ms	6468 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q,k,a[N],ind,x,l,r,t[2][4*N];
void update(int u,int ind,int l,int r,int val,int p) {

	if(l>ind || r<ind) 
      return;
	if(ind<=l && r<=ind) {
		t[p][u]^=val;
		return;
	}
	int mid=(l+r)/2;
	update(2*u,ind,l,mid,val,p);
	update(2*u+1,ind,mid+1,r,val,p);
	t[p][u]=t[p][2*u]^t[p][2*u+1];
}
int getans(int u,int start,int e,int l,int r,int p) {

	if(l>e || r<start) return 0;
	if(start<=l && r<=e) {
		return t[p][u];
	}
	int mid=(l+r)/2;
	return getans(2*u,start,e,l,mid,p)^
	       getans(2*u+1,start,e,mid+1,r,p);
}

int main() {
	cin>>n>>q;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		if(i%2==1) update(1,i,1,n,a[i],1);
		else update(1,i,1,n,a[i],0);

	}
	for(k=1; k<=q; k++) {
		cin>>x;
		if(x==1) {
			cin>>ind>>x;
			if(ind%2==0) update(1,ind,1,n,a[ind]^x,0);
			else update(1,ind,1,n,a[ind]^x,1);
			a[ind]=x;
		} else {
			cin>>l>>r;
			if((r-l+1)%2==0) cout<<0<<" ";
			else {

				cout<<getans(1,l,r,1,n,r%2)<<" ";
			}
		}
	}
}

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