Submission #255974

#	Time	Username	Problem	Language	Result	Execution time	Memory
255974		jdh	XORanges (eJOI19_xoranges)	C++17	100 / 100	181 ms	13464 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
vector<int> segt0,segt1,a;
void build(int idx,int b,int e){
  if(b == e){
    if(b&1) segt1[idx] = a[b];
    else segt0[idx] = a[b];
    return;
  }
  int mid = (b+e)/2;
  build(2*idx,b,mid);
  build(2*idx+1,mid+1,e);
  segt0[idx] = segt0[2*idx]^segt0[2*idx+1];
  segt1[idx] = segt1[2*idx]^segt1[2*idx+1];
}
void update(int idx,int b,int e,int pos,int val){
  if(b == e){
    if(b&1) segt1[idx] = val;
    else segt0[idx] = val;
    return;
  }
  int mid = (b+e)/2;
  if(pos <= mid) update(2*idx,b,mid,pos,val);
  else update(2*idx+1,mid+1,e,pos,val);
  segt0[idx] = segt0[2*idx]^segt0[2*idx+1];
  segt1[idx] = segt1[2*idx]^segt1[2*idx+1];
}
int query0(int idx,int b,int e,int l,int r){
  if(r < b or e < l or r < l) return 0;
  if(l <= b and e <= r) return segt0[idx];
  int mid = (b+e)/2;
  int s1 = query0(2*idx,b,mid,l,min(mid,r));
  int s2 = query0(2*idx+1,mid+1,e,max(l,mid+1),r);
  return s1^s2;
}
int query1(int idx,int b,int e,int l,int r){
  if(r < b or e < l or r < l) return 0;
  if(l <= b and e <= r) return segt1[idx];
  int mid = (b+e)/2;
  int s1 = query1(2*idx,b,mid,l,min(mid,r));
  int s2 = query1(2*idx+1,mid+1,e,max(l,mid+1),r);
  return s1^s2;
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,q;
  cin >> n >> q;
  segt0.resize(4*n+5);
  segt1.resize(4*n+5);
  a.resize(n+1);
  for(int i = 1; i <= n; ++i) cin >> a[i];
  build(1,1,n);
  while(q--){
    int op;
    cin >> op;
    if(op == 1){
      int pos,val;
      cin >> pos >> val;
      update(1,1,n,pos,val);
    }
    else{
      int l,r;
      cin >> l >> r;
      if((r-l)&1) cout << "0\n";
      else{
        if(l&1) cout << query1(1,1,n,l,r) << '\n';
        else cout << query0(1,1,n,l,r) << '\n';
      }
    }
  }
  return 0;
}

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