Submission #254493

#	Time	Username	Problem	Language	Result	Execution time	Memory
254493		lani1akea	XORanges (eJOI19_xoranges)	C++17	0 / 100	136 ms	6732 KiB

xoranges

#include <bits/stdc++.h>

#define F first
#define S second
#define ll long long
#define pb push_back
#define endl '\n'

using namespace std;

const int MOD = 1e9 + 7;
const int N = 2 * 1e5 + 1;

int n, q, a[N], t1[4*N], t2[4*N], ty;
void build(int v, int tl, int tr) {
  if (tl == tr) {
    if (tl % 2 ) t1[v] = a[tl];
    else t2[v] = a[tl];
    return;
  }
  int tm = (tl + tr) / 2;
  build(v*2, tl, tm); build(v*2+1, tm+1, tr);
  t1[v] = t1[v*2] ^ t1[v*2+1];
  t2[v] = t2[v*2] ^ t2[v*2+1];
}

int get(int v, int tl, int tr, int l, int r, int type) {
  if (l > r) return 0;
  if (tl >= l and tr <= r) {
    if (type == 1) return t1[v];
    else return t2[v];
  }
  int tm = (tl + tr) / 2;
  return get(v*2, tl, tm, l, min(tm, r), type) ^ get(v*2+1, tm+1, tr, max(tm+1, tl), tr, type);
}

void update(int v, int tl, int tr, int pos, int new_value) {
  if (tl == tr) {
    if (pos % 2) t1[v] = new_value;
    else t2[v] = new_value;
    return;
  }
  int tm = (tl + tr) / 2;
  if (pos <= tm) update(v*2, tl, tm, pos, new_value);
  else update(v*2+1, tm+1, tr, pos, new_value);
  t1[v] = t1[v*2] ^ t1[v*2+1];
  t2[v] = t2[v*2] ^ t2[v*2+1];
}

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

  cin >> n >> q;

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

  build(1, 0, n - 1);

  while (q--) {
    int ty, i, j;
    cin >> ty >> i >> j;
    if (ty == 1) update(1, 0, n - 1, --i, j);
    else if(i % 2 != j % 2) cout << "0\n";
    else if(i % 2) cout << get(1, 0, n-1, i-1, j-1, 2) << endl;
    else cout << get(1, 0, n-1, i-1, j-1, 1) << endl;
  }
}

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