Submission #841575

#	Time	Username	Problem	Language	Result	Execution time	Memory
841575		WLZ	XORanges (eJOI19_xoranges)	C++17	100 / 100	219 ms	45492 KiB

xoranges

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

struct node {
  int i, j;
  int val;
  node *left, *right;
};

node *build(int i, int j, const vector<int>& a) {
  if (i == j) {
    return new node{i, j, a[i], nullptr, nullptr};
  } 
  node *left = build(i, (i + j) / 2, a);
  node *right = build((i + j) / 2 + 1, j, a);
  return new node{i, j, (left->val ^ right->val), left, right};
}

int query(node *cur, int i, int j) {
  if (cur->j < i || cur->i > j) {
    return 0;
  }
  if (cur->i >= i && cur->j <= j) {
    return cur->val;
  }
  return query(cur->left, i, j) ^ query(cur->right, i, j);
}

void update(node *cur, int i, int new_val) {
  if (cur->j < i || cur->i > i) {
    return;
  }
  if (cur->i == i && cur->j == i) {
    cur->val = new_val;
    return;
  } 
  update(cur->left, i, new_val);
  update(cur->right, i, new_val);
  cur->val = cur->left->val ^ cur->right->val;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> odd_in(n + 1), even_in(n + 1);
  for (int i = 1; i <= n; i++) {
    if (i % 2 == 0) {
      cin >> even_in[i];
    } else {
      cin >> odd_in[i];
    }
  }
  node *odd = build(1, n, odd_in);
  node *even = build(1, n, even_in);
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int i, j;
      cin >> i >> j;
      if (i % 2 == 0) {
        update(even, i, j);
      } else {
        update(odd, i, j);
      }
    } else {
      int l, u;
      cin >> l >> u;
      if ((u - l + 1) % 2 == 0) {
        cout << 0 << '\n';
        continue;
      }
      if (l % 2 == 0) {
        cout << query(even, l, u) << '\n';
      } else {
        cout << query(odd, 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