Submission #286231

#	Time	Username	Problem	Language	Result	Execution time	Memory
286231		lukameladze	XORanges (eJOI19_xoranges)	C++14	100 / 100	676 ms	16120 KiB

xoranges

# include <bits/stdc++.h>
using namespace std;
long long n,q,a[300005],ty,w,idx,val,tree[5][1200005],ans,x,ri,le;
void update(int node, int le, int ri, int idx, int val, int w)
{
       if (le>idx || ri<idx) return;
     if (idx==le && idx==ri)
     {
          tree[w][node]^=val;
          return ;
     }
     long long mid=(le+ri)/2;
     update(2*node, le, mid, idx, val , w);
     update(2*node+1, mid+1, ri , idx, val, w);
     tree[w][node]=tree[w][2*node]^tree[w][2*node+1];
}
long long getans(int node, int le, int ri, int start, int end, int w)
{
	if (le>end || ri<start) return 0;
	if (le>=start && ri<=end) 
	{
		return tree[w][node];
	}
	long long mid=(le+ri)/2;
	long long p1=getans(2*node, le, mid, start, end,w);
	 long long p2=getans(2*node+1, mid+1, ri, start, end,w);
	return p1^p2;
}
int main()
{
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
     cin>>n>>q;
     for (int i=1; i<=n; i++)
     {
          cin>>a[i];
          if (i%2==1)
          {
               update(1,1,n,i,a[i],1);
          }
          else
          {
               update(1,1,n, i,a[i],0);
          }
     }
     //cout<<1<<endl;
     for (int i=1; i<=q; i++)
     {
          cin>>ty;
          if (ty==1)
          {
               cin>>idx>>val;
               w=val^a[idx];
               update(1,1,n, idx, w, idx%2);
               a[idx]=val;
          }
          else
          {
               cin>>le>>ri;
               x=(ri-le+1);
               if (x%2==0)
               {
                    cout<<0<<endl;
                    continue;
               }//cout<<le<<" "<<ri<<"   ";
                    cout<<getans(1,1,n,le,ri,le%2)<<endl;
          }
          
     }
}

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