Advertisement
mickypinata

FORCE-T0339D: Xenia and Bit Operations

Nov 10th, 2021
461
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int logN = 17;
  5.  
  6. int sm[1 << (logN + 1)];
  7.  
  8. int main(){
  9.  
  10.     int ex, Q;
  11.     scanf("%d%d", &ex, &Q);
  12.     for(int i = (1 << ex); i < (1 << (ex + 1)); ++i){
  13.         scanf("%d", &sm[i]);
  14.     }
  15.     bool doOr = true;
  16.     for(int e = ex - 1; e >= 0; --e){
  17.         for(int i = (1 << e); i < (1 << (e + 1)); ++i){
  18.             if(doOr){
  19.                 sm[i] = sm[i << 1] | sm[(i << 1) | 1];
  20.             } else {
  21.                 sm[i] = sm[i << 1] ^ sm[(i << 1) | 1];
  22.             }
  23.         }
  24.         doOr = !doOr;
  25.     }
  26.     while(Q--){
  27.         int idx, x;
  28.         scanf("%d%d", &idx, &x);
  29.         idx += (1 << ex) - 1;
  30.         sm[idx] = x;
  31.         doOr = true;
  32.         for(int i = idx >> 1; i >= 1; i >>= 1){
  33.             if(doOr){
  34.                 sm[i] = sm[i << 1] | sm[(i << 1) | 1];
  35.             } else {
  36.                 sm[i] = sm[i << 1] ^ sm[(i << 1) | 1];
  37.             }
  38.             doOr = !doOr;
  39.         }
  40.         cout << sm[1] << '\n';
  41.     }
  42.  
  43.     return 0;
  44. }
  45.  
Advertisement
RAW Paste Data Copied
Advertisement