Submission #752771

#	Time	Username	Problem	Language	Result	Execution time	Memory
752771		emad234	XORanges (eJOI19_xoranges)	C++17	100 / 100	635 ms	15688 KiB

xoranges

#include <bits/stdc++.h>
#define all(v) ((v).begin(),(v).end())
typedef long long ll;
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 4e6 + 5;
struct tree{
  ll odd,even,size;
};
tree seg[mxN] = {};
ll N,s,e,val;
tree combine(tree a,tree b){
  tree c;
  c.size = a.size + b.size;
  if(a.size % 2){
    c.odd = (a.odd ^ b.even);
    c.even = (a.even ^ b.odd);
  }else{
    c.odd = (a.odd ^ b.odd);
    c.even = (a.even ^ b.even);
  }
  return c;
}
tree query(ll l = 1,ll r = N,ll ind = 1){
  if(l > e || r < s) return {0,0,0};
  if(l >= s && r <= e) return seg[ind];
  ll md = (l + r) / 2;
  return combine(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void update(ll ind){
  ind += N;
  seg[ind] = {val,0,1};
  ind /= 2;
  while(ind){
    seg[ind] = combine(seg[ind * 2],seg[ind * 2 + 1]);
    ind /= 2;
  }
}
signed main() {
  ll n,q;
  cin >>n>>q;
  N = exp2(ceil(log2(n)));
  for(ll i = 0;i < n;i++){
    cin >>val;
    update(i);
  }
  while(q--){
    ll op,i,j;
    cin >>op>>i>>j;
    if(op == 1){
      val = j;
      i--;
      update(i);
    }else{
      s = i;e = j;
      ll ans =query().odd;
      if((j - i + 1) % 2 == 0) ans = 0;
      cout<<ans<<'\n';
    }
  }
}

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