fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. const int MAXN = 1 << 17; // Số phần tử tối đa (2^17)
  6. long long tree[4 * MAXN]; // Mảng lưu trữ cây phân đoạn
  7. int n, m; // Số cấp độ và số truy vấn
  8. int N; // Tổng số phần tử (2^n)
  9. vector<long long> arr; // Dãy số ban đầu
  10.  
  11. // Hàm xây dựng cây phân đoạn
  12. void build(int node, int left, int right, int height) {
  13.     if (left == right) {
  14.         tree[node] = arr[left];
  15.     } else {
  16.         int mid = (left + right) / 2;
  17.         build(2 * node, left, mid, height - 1);
  18.         build(2 * node + 1, mid + 1, right, height - 1);
  19.         if (height % 2 == 0) {
  20.             // Mức chẵn -> Phép OR
  21.             tree[node] = tree[2 * node] | tree[2 * node + 1];
  22.         } else {
  23.             // Mức lẻ -> Phép XOR
  24.             tree[node] = tree[2 * node] ^ tree[2 * node + 1];
  25.         }
  26.     }
  27. }
  28.  
  29. // Hàm cập nhật cây phân đoạn
  30. void update(int node, int left, int right, int index, long long value, int height) {
  31.     if (left == right) {
  32.         tree[node] = value;
  33.     } else {
  34.         int mid = (left + right) / 2;
  35.         if (index <= mid) {
  36.             update(2 * node, left, mid, index, value, height - 1);
  37.         } else {
  38.             update(2 * node + 1, mid + 1, right, index, value, height - 1);
  39.         }
  40.         if (height % 2 == 0) {
  41.             // Mức chẵn -> Phép OR
  42.             tree[node] = tree[2 * node] | tree[2 * node + 1];
  43.         } else {
  44.             // Mức lẻ -> Phép XOR
  45.             tree[node] = tree[2 * node] ^ tree[2 * node + 1];
  46.         }
  47.     }
  48. }
  49.  
  50. int main() {
  51.     ios::sync_with_stdio(false);
  52.     cin.tie(nullptr);
  53.  
  54.     cin >> n >> m;
  55.     N = 1 << n;
  56.     arr.resize(N + 1); // Chỉ số bắt đầu từ 1
  57.     for (int i = 1; i <= N; ++i) {
  58.         cin >> arr[i];
  59.     }
  60.  
  61.     build(1, 1, N, n);
  62.  
  63.     for (int i = 0; i < m; ++i) {
  64.         int p;
  65.         long long b;
  66.         cin >> p >> b;
  67.         update(1, 1, N, p, b, n);
  68.         cout << tree[1] << '\n';
  69.     }
  70.  
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
2 4
1 6 3 5
1 4
3 4
1 2
1 2
stdout
copy 
6
3
5
5
https://ideone.com/vfwqMZ
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!