Submission #254468

#	Time	Username	Problem	Language	Result	Execution time	Memory
254468		lani1akea	XORanges (eJOI19_xoranges)	C++17	0 / 100	132 ms	9976 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], t[4 * N], ty;
void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v] = a[tl];
    return;
  }
  int tm = (tl + tr) / 2;
  build(v*2, tl, tm); build(v*2+1, tm+1, tr);
  t[v] = t[v*2] ^ t[v*2+1];
}

int solve(int v, int tl, int tr, int l, int r) {
  if (l > r) return 0;
  if (tl == l and tr == r)
    return t[v];

  int tm = (tl + tr) / 2;
  return solve(v*2, tl, tm, l, min(tm, r)) ^ solve(v*2+1, tm+1, tr, max(tm+1, tl), tr);
}

void update(int v, int tl, int tr, int pos, int new_value) {
  if (tl == tr) {
    t[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);
  t[v] = t[v*2] ^ t[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--) {
    cin >> ty;
    if (ty & 1) {
      int l, r;
      cin >> l >> r;
      update(1, 0, n - 1, --l, r);
    } else {
      int l, r;
      cin >> l >> r;
      cout << solve(1, 0, n-1, --l, --r) << endl;
    }
  }
}

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