Submission #935085

#	Time	Username	Problem	Language	Result	Execution time	Memory
935085		ind1v	XORanges (eJOI19_xoranges)	C++11	100 / 100	105 ms	8788 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

struct fenwick_tree {
  int f[N];
  
  fenwick_tree() {
    memset(f, 0, sizeof(f));
  }
  
  void upd(int i, int x) {
    for (; i < N; i += i & -i) {
      f[i] ^= x;
    }
  }
  
  int get(int i) {
    int res = 0;
    for (; i > 0; i -= i & -i) {
      res ^= f[i];
    }
    return res;
  }
  
  int get(int l, int r) {
    return get(r) ^ get(l - 1);
  }
};

int n, q;
int a[N];
fenwick_tree ft[2];

void upd(int i, int j) {
  ft[i & 1].upd(i, a[i]);
  a[i] = j;
  ft[i & 1].upd(i, a[i]);
}

int get(int l, int u) {
  if ((l & 1) != (u & 1)) {
    return 0;
  }
  return ft[l & 1].get(l, u);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    ft[i & 1].upd(i, a[i]);
  }
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int i, j;
      cin >> i >> j;
      upd(i, j);
    } else if (t == 2) {
      int l, u;
      cin >> l >> u;
      cout << get(l, u) << '\n';
    }
  }
  return 0;
}

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