제출 #676394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676394		Truitadepatates	XORanges (eJOI19_xoranges)	C++14	100 / 100	139 ms	10364 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;

void build(vector<int>& a, vector<int>& segtree, int x, int l, int r){
  if (l == r){
    segtree[x] = a[l];
    return;
  }
  int m = (l+r)/2;
  build(a, segtree, 2*x, l, m);
  build(a, segtree, 2*x+1, m+1, r);
  segtree[x] = segtree[2*x]^segtree[2*x+1];
}

void update(vector<int>&a, vector<int>& segtree, int x, int l, int r, int i, int v){
  if (i < l or i > r) return;
  else if (l == r){
    segtree[x] = v;
    a[l] = v;
  }
  else{
    int m = (l+r)/2;
    if (i <= m) update(a, segtree, 2*x, l, m, i, v);
    else update(a, segtree, 2*x+1, m+1, r, i, v);
    segtree[x] = segtree[2*x]^segtree[2*x+1];
  }
}

int range(vector<int>& segtree, int x, int l, int r, int lx, int rx){
  if (l >= lx && r <= rx) return segtree[x];
  else if (l > rx or r < lx) return 0;
  else{
    int m = (l+r)/2;
    int xor1 = range(segtree, 2*x, l, m, lx, rx);
    int xor2 = range(segtree, 2*x+1, m+1, r, lx, rx);
    return xor1^xor2;
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  int n1, n2;
  if (n%2 == 0){
    n1 = n/2;
    n2 = n1;
  }
  else{
    n1 = n/2 + 1;
    n2 = n/2;
  }
  vector<int> aEven(n1);
  vector<int> aOdd(n2);
  vector<int> SegtreeEven(4*n1, 0);
  vector<int> SegtreeOdd(4*n2, 0);
  for (int i = 0; i < n; i++){
    if (i%2 == 0) cin >> aEven[i/2];
    else cin >> aOdd[i/2];
  }
  build(aEven, SegtreeEven, 1, 0, n1-1);
  if (n2 >= 1){
    build(aOdd, SegtreeOdd, 1, 0, n2-1);
  }
  int op, i, v;
  while (q--){
    cin >> op >> i >> v;
    if (op == 1){
      if ((i-1)%2 == 0) update(aEven, SegtreeEven, 1, 0, n1-1, (i-1)/2, v);
      else update(aOdd, SegtreeOdd, 1, 0, n2-1, (i-1)/2, v);
    }
    else{
      int Range = v-i+1;
      if (Range%2 == 0) cout << 0 << "\n";
      else if ((i-1)%2 == 0) cout << range(SegtreeEven, 1, 0, n1-1, (i-1)/2, (v-1)/2) << "\n";
      else cout << range(SegtreeOdd, 1, 0, n2-1, (i-1)/2, (v-1)/2) << "\n";
    }
  }
  return 0;
}

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