Love no Exist

Codeforces 339D – Xenia and Bit Operations

  • No Comments

Tóm tắt đề bài

Bài toán yêu cầu quản lý một cây Segment Tree để thực hiện hai loại thao tác:

  1. Cập nhật giá trị tại vị trí chỉ định:
    • Input: p, b (cập nhật giá trị tại vị trí p thành b).
  2. Tìm giá trị của nút gốc:
    • Output: giá trị của nút gốc của cây.

Cây được xây dựng dựa trên các phép OR và XOR, xen kẽ giữa các tầng của cây (tầng chẵn sử dụng XOR, tầng lẻ sử dụng OR).

Ví dụ

Input:

C++
2 4
1 6 3 5
1 4
3 4
1 2
1 2

Output:

C++
1
3
3
3

Hướng dẫn giải

(Bữa nảo rảnh thì cập nhật sau)

Code

C++
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1 << 17; // Maximum number of elements (2^17)
int tree[4 * MAXN]; // Segment tree
int a[MAXN]; // Original array
int n, m; // n: log2(N), m: number of queries

void build(int node, int l, int r, int level) {
    if (l == r) {
        tree[node] = a[l];
    } else {
        int mid = (l + r) / 2;
        build(2 * node, l, mid, level + 1);
        build(2 * node + 1, mid + 1, r, level + 1);
        if (level % 2 == 0) {
		        // XOR operation
            tree[node] = tree[2 * node] ^ tree[2 * node + 1];
        } else {
		        // OR operation
            tree[node] = tree[2 * node] | tree[2 * node + 1];
        }
    }
}

void update(int node, int l, int r, int pos, int val, int level) {
    if (l == r) {
        tree[node] = val;
    } else {
        int mid = (l + r) / 2;
        if (pos <= mid)
            update(2 * node, l, mid, pos, val, level + 1);
        else
            update(2 * node + 1, mid + 1, r, pos, val, level + 1);
        if (level % 2 == 0) {
		        // XOR operation
            tree[node] = tree[2 * node] ^ tree[2 * node + 1];
        } else {
		        // OR operation
            tree[node] = tree[2 * node] | tree[2 * node + 1];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    int N = 1 << n; // Total number of elements
    for (int i = 1; i <= N; ++i) {
        cin >> a[i];
    }
    build(1, 1, N, 0);

    while (m--) {
        int p, b;
        cin >> p >> b;
        update(1, 1, N, p, b, 0);
        cout << tree[1] << '\\n';
    }

    return 0;
}