Submission #1220624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220624		Solikha	XORanges (eJOI19_xoranges)	C++17	100 / 100	179 ms	7284 KiB

xoranges

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
using namespace std;
#define int long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ss second
#define ff first
#define pb push_back 
using ull = unsigned long long;

struct Node{
  int val;
};

Node make_node(int x = 0){
  return Node{x};
}

Node merge(const Node &a, const Node &b){
  return Node{(a.val ^ b.val)};
}

struct Segtree{
  int n, N; 
  vector<Node> tree;
  Segtree(vector<Node> &a) : n(a.size()){
    N = 1;
    while(N < n) N <<= 1;
    tree.assign(2 * N, make_node());
    for(int i = 0; i < n; i++) tree[i + N] = a[i];
    for(int i = N - 1; i >= 1; i--) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
  }

  void update(int i, Node x){
    i += N; tree[i] = x;
    for(i >>= 1; i >= 1; i >>= 1) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
  }

  Node get(int l, int r){
    Node ans = make_node();
    for(l += N, r += N; l < r; l >>= 1, r >>= 1){
      if(l & 1) ans = merge(ans, tree[l++]);
      if(r & 1) ans = merge(ans, tree[--r]);
    }
    return ans;
  }
};


void solve()
{
  int n, q; cin >> n >> q;
  vector<Node> a(n / 2), b((n + 1) / 2);
  int x = 0, y = 0;
  for(int i = 1; i <= n; i++){
    if(i & 1){
      cin >> b[y].val; y++;
    }else{
      cin >> a[x].val; x++;
    }
  }
  Segtree even(a);
  Segtree odd(b);
  while(q--){
    int t; cin >> t;
    if(t == 1){
      int i;
      Node x; cin >> i >> x.val;
      if(i & 1) odd.update(i / 2, x);
      else even.update(i / 2 - 1, x);
    }else{
      int l, r; cin >> l >> r;
      int ans = 0;
      if((r - l + 1) & 1){
        if(l & 1){
          ans = odd.get(l / 2, r / 2 + 1).val;
        }else{
          ans = even.get(l / 2 - 1, r / 2).val;
        }
      }
      cout << ans << endl;
    }
  }
}
 
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  int t = 1; //cin >> t;
  while(t--){
    solve();
    cout << endl;
  }
  return 0;
}

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