제출 #775455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
775455		SalihSahin	XORanges (eJOI19_xoranges)	C++14	100 / 100	295 ms	6468 KiB

xoranges

#include <bits/stdc++.h>
#define pb push_back
#define fastio cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0)
using namespace std;

const int N = 5e3 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9*2;


struct SegT{
  vector<int> tree;

  void init(int n){
    tree.resize(n*4);
  }

  void build(vector<int> &a, int v, int tl, int tr){
    if(tl == tr) tree[v] = a[tl];
    else{
        int tm = (tl + tr)/2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        tree[v] = tree[v*2] ^ tree[v*2+1];
    }
  }

  int query(int v, int tl, int tr, int l, int r){
    if(l > r) return 0;
    if(l == tl && r == tr) return tree[v];
    int tm = (tl + tr)/2;
    return query(v*2, tl, tm, l, min(tm, r)) ^ query(v*2+1, tm+1, tr, max(l, tm+1), r);
    //return query(v*2, tl, tm, l, r) ^ query(v*2+1, tm+1, tr, l, r);
  }

  void update(int v, int tl, int tr, int pos, int val){
    if(tl == tr) tree[v] = val;
    else{
        int tm = (tl + tr)/2;

        if(pos <= tm){
            update(v*2, tl, tm, pos, val);
        }
        else update(v*2+1, tm+1, tr, pos, val);

        tree[v] = tree[v*2] ^ tree[v*2+1];
    }
  }
};

int main(){
  fastio;
  SegT segeven, segodd;
  int n, q;
  cin>>n>>q;
  vector<int> a(n);
  vector<int> odd, even;
  for(int i = 0; i < n; i++){
    cin>>a[i];
    if(i%2) odd.pb(a[i]);
    else even.pb(a[i]);
  }
  segeven.init(even.size());
  segeven.build(even, 1, 0, even.size()-1);

  segodd.init(odd.size());
  segodd.build(odd, 1, 0, odd.size()-1);

  while(q--){
    int x;
    cin>>x;
    if(x == 1){
        int i, nv;
        cin>>i>>nv;
        i--;

        if(i%2) segodd.update(1, 0, odd.size()-1, i/2, nv);
        else segeven.update(1, 0, even.size()-1, i/2, nv);
    }
    else{
        int l, u;
        cin>>l>>u;
        l--, u--;

        if((u-l+1)%2){
            int ql = l/2, qu = u/2;
            if(l&1) cout<<segodd.query(1, 0, odd.size()-1, ql, qu)<<endl;
            else cout<<segeven.query(1, 0, even.size()-1, ql, qu)<<endl;
        }
        else cout<<0<<endl;
    }
  }

  return 0;
}

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