Advertisement
YEZAELP

D. Xenia and Bit Operations

Jan 30th, 2021 (edited)
162
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int tree[2*(1<<17)];
  6. int ar[1<<17];
  7. int n, m, N;
  8.  
  9. int comb(int a, int b, int level){
  10.     if((N - level) % 2 == 0)
  11.         return a | b;
  12.     return a ^ b;
  13. }
  14.  
  15. int build(int i, int l, int r, int level){
  16.     if(r == l)
  17.         return tree[i] = ar[l];
  18.     int mid = (l + r) / 2;
  19.     return tree[i] = comb(build(2*i, l, mid, level+1), build(2*i+1, mid+1, r, level+1), level);
  20. }
  21.  
  22. int query(int i, int l, int r, int p, int b, int level){
  23.     if(r == l)
  24.         return tree[i] = b;
  25.     int mid = (l + r) / 2;
  26.     if(p <= mid)
  27.         return tree[i] = comb(query(2*i, l, mid, p, b, level+1), tree[2*i+1], level);
  28.     else
  29.         return tree[i] = comb(query(2*i+1, mid+1, r, p, b, level+1), tree[2*i], level);
  30. }
  31.  
  32. int main(){
  33.  
  34.     scanf("%d%d", &n, &m);
  35.  
  36.     N = n;
  37.     n = 1 << n;
  38.  
  39.     for(int i=0;i<n;i++){
  40.         scanf("%d", &ar[i]);
  41.     }
  42.  
  43.     build(1, 0, n-1, 1);
  44.  
  45.     /*for(int i=1;i<2*n;i++){
  46.         printf("%d ", tree[i]);
  47.     }*/
  48.  
  49.     for(int i=1;i<=m;i++){
  50.         int p, b;
  51.         scanf("%d%d", &p, &b);
  52.         printf("%d\n", query(1, 0, n, p, b, 1));
  53.     }
  54.  
  55.     return 0;
  56. }
Advertisement
RAW Paste Data Copied
Advertisement