제출 #1325927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325927		djsksbrbf	XORanges (eJOI19_xoranges)	C++20	100 / 100	232 ms	21388 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define pb push_back
const int MOD = 1e9 + 7;
const int MAX = 2e5 + 5;
#define int ll

int sege[4*MAX], sego[4*MAX];
vector <int> ev, od;
int a[MAX];

void upde(int l, int r, int id, int val, int pos){
   if(l == r){
      sege[pos] = val;
      ev[id] =val;
      return;
   }
   
   int mid = (l + r) >> 1;
   if(id <= mid)upde(l, mid, id, val, 2*pos);
   else upde(mid + 1, r, id, val, 2*pos + 1);
   
   sege[pos] = (sege[2*pos] ^ sege[2*pos + 1]);
}

void updo(int l, int r, int id, int val, int pos){
   if(l == r){
      sego[pos] = val;
      od[id] = val;
      return;
   }
   
   int mid = (l + r) >> 1;
   if(id <= mid)updo(l, mid, id, val, 2*pos);
   else updo(mid + 1, r, id, val, 2*pos + 1);
   
   sego[pos] = (sego[2*pos] ^ sego[2*pos + 1]);
}

int queo(int l, int r, int tl, int tr, int pos){
   if(r < tl || tr < l || tr< tl)return 0;
   if(tl <= l && r <= tr)return sego[pos];
   
   int mid = ( l + r) >> 1;
   return (queo(l, mid, tl, tr, 2*pos)^queo(mid + 1, r, tl, tr, 2*pos + 1));
}

int quee(int l, int r, int tl, int tr, int pos){
   if(r < tl || tr < l || tr< tl)return 0;
   if(tl <= l && r <= tr)return sege[pos];
   
   int mid = ( l + r) >> 1;
   return (quee(l, mid, tl, tr, 2*pos)^quee(mid + 1, r, tl, tr, 2*pos + 1));
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   
   int n, q; cin >> n >> q;
   for(int i = 1 ; i <= n ; i++)cin >> a[i];
   
   map <int, int> pose, poso;
   for(int i = 1  ; i <= n ; i++){
      (i % 2 ? od : ev).pb(a[i]);
      if(i % 2){
         poso[i] = (int)od.size() - 1;
      }
      else pose[i] = (int)ev.size() - 1;
   }
   
   for(int i = 0 ; i < (int)od.size() ; i++){
      updo(0, (int)od.size() - 1, i, od[i], 1);
   }
   
   for(int i = 0 ; i < (int)ev.size() ; i++){
      upde(0, (int)ev.size() - 1, i, ev[i], 1);
   }
   
   while(q--){
      int op, x, y; cin >> op >>x >> y;
      if(op == 1){
         if(x % 2)updo(0, (int)od.size() - 1, poso[x], y, 1);
         else upde(0, (int)ev.size() - 1, pose[x], y, 1);
      }
      else{
         int l = x, r = y;
         
         if((r - l + 1) % 2){
            if(r % 2){
               cout << queo(0, (int)od.size() - 1, poso[l], poso[r], 1) << '\n';
            }
            else cout << quee(0, (int)ev.size() - 1, pose[l], pose[r], 1) << '\n';
         }
         else cout << 0 << '\n';
      }
   }
   
   return 0;
}

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