Submission #811584

#	Time	Username	Problem	Language	Result	Execution time	Memory
811584		taher	XORanges (eJOI19_xoranges)	C++17	0 / 100	123 ms	14980 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "C:\GCC\debug.h"
#else
#define debug(...) void(42)
#endif

struct SegTree {
  public:
  int n;
  vector<array<int, 2>> st;
  vector<int> init;

  SegTree(int _n, vector<int> _init) : n(_n), init(_init) {
    st.resize(4 * n);
  }

  array<int, 2> Combine(array<int, 2> x, array<int, 2> y) {
    array<int, 2> z;
    z[0] = x[0] ^ y[0];
    z[1] = x[1] ^ y[1];
    return z;
  }

  void update(int v, int l, int r, int pos, int nv) {
    if (l == r) {
      if (l % 2 == 0) {
        st[v][0] = nv;
      } else {
        st[v][1] = nv;
      }
      return ;
    }

    int mid = l + (r - l) / 2;
    if (pos <= mid) {
      update(v * 2, l, mid, pos, nv);
    } else {
      update(v * 2 + 1, mid + 1, r, pos, nv);
    }
    st[v] = Combine(st[v * 2], st[v * 2 + 1]);
  }

  int get(int v, int l, int r, int low, int high, int parity) {
    if (l == low && r == high) {
      return st[v][parity];
    }

    int mid = l + (r - l) / 2;

    if (high <= mid) {
      return get(v * 2, l, mid, low, high, parity);
    } else if (low > mid) {
      return get(v * 2 + 1, mid + 1, r, low, high, parity);
    }
    return get(v * 2, l, mid, low, mid, parity) ^
          get(v * 2 + 1, mid + 1, r, mid + 1, high, parity);
  }

  void build(int v, int l, int r) {
    if (l == r) {
      if (l % 2 == 0) {
        st[v][0] = init[l];
        st[v][1] = 0;
      } else {
        st[v][0] = 0;
        st[v][1] = init[l];
      }
      return ;
    }

    int mid = l + (r - l) / 2;
    build(v * 2, l, mid);
    build(v * 2 + 1, mid + 1, r);
    st[v] = Combine(st[v * 2], st[v * 2 + 1]);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;

  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  SegTree st(n, a);
  st.build(1, 0, n - 1);

  for (int i = 0; i < q; i++) {
    int type;
    cin >> type;

    if (type == 1) {
      int x, y;
      cin >> x >> y;
      --x;
      a[x] = y;
      st.update(1, 0, n - 1, x, y);
    } else {
      int l, r;
      cin >> l >> r;
      --l, --r;

      int seg_length = r - l + 1;
      cout << st.get(1, 0, n - 1, l, r, seg_length % 2 == l % 2) << '\n';
    }
  }
  return 0;
}

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