Submission #966225

#	Time	Username	Problem	Language	Result	Execution time	Memory
966225		vjudge1	XORanges (eJOI19_xoranges)	C++17	100 / 100	437 ms	14308 KiB

xoranges

#include<bits/stdc++.h>
using namespace std;
long long n,q,a[1000001],b[1000001],c[1000001],tc[4000001],tl[4000001],db=1,dc=1;
void build(long long id,long long l,long long r)
{
	if(l==r)
	{
		if(l%2==0)
		{
			tc[id]=a[l];
			tl[id]=0;
		}
		else
		{
			tc[id]=0;
			tl[id]=a[l];
		}
		return ;
	}
	long long mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	tc[id]=tc[id*2]^tc[id*2+1];
	tl[id]=tl[id*2]^tl[id*2+1];
}
void update(long long id,long long l,long long r ,long long pos,long long w)
{
	if(l>pos||r<pos) return ;
	if(l==r)
	{
		if(l%2==1)
		{
//			tl[id]=a[pos];
			tl[id]=w;
			return ;
		}
		else
		{
//			tc[id]=a[pos];
			tc[id]=w;
			return ;
		}
	}
	long long mid=(l+r)/2;
	update(id*2,l,mid,pos,w);
	update(id*2+1,mid+1,r,pos,w);
	tc[id]=tc[id*2]^tc[id*2+1];
	tl[id]=tl[id*2]^tl[id*2+1];
}
long long getc(long long id,long long l,long long r,long long u,long long v)
{
	if(l>v||r<u) return 0;
	if(u<=l&&r<=v)
	{
		return tc[id];
	}
	long long mid=(l+r)/2;
	return getc(id*2,l,mid,u,v)^getc(id*2+1,mid+1,r,u,v);
}
long long getl(long long id,long long l,long long r,long long u,long long v)
{
	if(l>v||r<u) return 0;
	if(u<=l&&r<=v)
	{
//		cout<<l<<" "<<r<<endl;
		return tl[id];
	}
	long long mid=(l+r)/2;
	return getl(id*2,l,mid,u,v)^getl(id*2+1,mid+1,r,u,v);
}

int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(q--)
	{
		long long tv;
		cin>>tv;
		if(tv==1)
		{
			long long pos,w;
			cin>>pos>>w;
			a[pos]=w;
			update(1,1,n,pos,w);
		}
		else
		{
			long long l,r;
			cin>>l>>r;
			if((r-l)%2==1)
			{
				cout<<0<<endl;
			}
			else
			{
				if(l%2==1)
				{
					cout<<getl(1,1,n,l,r)<<endl;
				}
				else cout<<getc(1,1,n,l,r)<<endl;
			}
		}
	}
	return 0;	
}

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