Submission #775227

#	Time	Username	Problem	Language	Result	Execution time	Memory
775227		vjudge1	XORanges (eJOI19_xoranges)	C++17	100 / 100	335 ms	9136 KiB

xoranges

#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);
//#define endl "\n"
#define ll long long
#define pb push_back
#define N 2000005
int seg[N*4],segment[N*4], ama[N],ancak[N];
inline void buid(int x,int l,int r){
	if(l>r)return;
	if(l==r){seg[x]=ama[l];return;}
	int m=(l+r)/2;
	buid(x*2,l,m);buid(x*2+1,m+1,r);
	seg[x]=seg[x*2]^seg[x*2+1];
}
inline void up(int x,int l,int r,int hedef,int val){
	if(l>r||l>hedef||r<hedef)return;
	if(l==r){seg[x]=val;return;}
	int m=(l+r)/2;
	up(x*2,l,m,hedef,val);up(x*2+1,m+1,r,hedef,val);
	seg[x]=seg[x*2]^seg[x*2+1];
}
inline int qu(int x,int l,int r,int s,int e){
	if(l>r||s>r||e<l)return 0;
	if(s<=l&&r<=e)return seg[x];
	int m=(l+r)/2;
	return qu(x*2,l,m,s,e)^qu(x*2+1,m+1,r,s,e);
}

inline void bui(int x,int l,int r){
	if(l>r)return;
	if(l==r){segment[x]=ancak[l];return;}
	int m=(l+r)/2;
	bui(x*2,l,m);bui(x*2+1,m+1,r);
	segment[x]=segment[x*2]^segment[x*2+1];
}
inline void update(int x,int l,int r,int hedef,int val){
	if(l>r||l>hedef||r<hedef)return;
	if(l==r){segment[x]=val;return;}
	int m=(l+r)/2;
	update(x*2,l,m,hedef,val);update(x*2+1,m+1,r,hedef,val);
	segment[x]=segment[x*2]^segment[x*2+1];
}
inline int quary(int x,int l,int r,int s,int e){
	if(l>r||s>r||e<l)return 0;
	if(s<=l&&r<=e)return segment[x];
	int m=(l+r)/2;
	return quary(x*2,l,m,s,e)^quary(x*2+1,m+1,r,s,e);
}
int main(){
	lalala;
	int n,q;cin>>n>>q;
	int ii=1,jj=1;
	for(int i=1;i<=n;i++){
		if(i%2){cin>>ama[ii];ii++;}
		else {cin>>ancak[jj];jj++;}
	}
	buid(1,1,ii);bui(1,1,jj);
	while(q--){
		int yes,x,y;cin>>yes>>x>>y;
		if(yes==1){
			if(x%2){
				up(1,1,ii,(x+1)/2,y);
			}
			else update(1,1,jj,(x+1)/2,y);
			continue;
		}
		if((y-x)%2){cout<<0<<endl;continue;}
		if(x%2)	cout<<qu(1,1,ii,(x+1)/2,(y+1)/2)<<endl;
		

		else cout<<quary(1,1,jj,(x+1)/2,(y+1)/2)<<endl;
	}
}

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