Submission #1143497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143497		fryingduc	XORanges (eJOI19_xoranges)	C++20	100 / 100	83 ms	8560 KiB

xoranges

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
int n, a[maxn];
int q;

struct segment_tree {
  vector<int> tree;
  
  segment_tree() {}
  segment_tree(int n) : tree(n * 4 + 6) {}
  
  void update(int pos, int val, int ind = 1, int l = 1, int r = n) {
    if(l == r) {
      tree[ind] = val;
      return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) update(pos, val, ind << 1, l, mid);
    else update(pos, val, ind << 1 | 1, mid + 1, r);
    tree[ind] = tree[ind << 1] ^ tree[ind << 1 | 1];
  }
  
  int get(int x, int y, int ind = 1, int l = 1, int r = n) {
    if(l > y || r < x) return 0;
    if(x <= l and r <= y) {
      return tree[ind];
    }
    int mid = (l + r) >> 1;
    return get(x, y, ind << 1, l, mid) ^ get(x, y, ind << 1 | 1, mid + 1, r);
  }
} st[2];

void solve() {
  cin >> n >> q;
  st[0] = st[1] = segment_tree(n);
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    st[i & 1].update(i, a[i]);
  }
  while(q--) {
    int op; cin >> op;
    if(op == 1) {
      int pos, val; cin >> pos >> val;
      st[pos & 1].update(pos, val);
    } else {
      int l, r; cin >> l >> r;
      if((l + r) & 1) {
        cout << 0 << '\n';
        continue;
      }
      cout << st[l & 1].get(l, r) << '\n';
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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