A9091 Xenia and Bit Operations

#include <bits/stdc++.h>
using namespace std;

/*
Xenia and Bit Operations：
  第 1 轮相邻两数取 OR，第 2 轮取 XOR，第 3 轮 OR……直到只剩一个数。
  线段树按层决定合并方式：叶子高度 0，父结点高度 h，
  h 为奇数用 OR，h 为偶数用 XOR（第一轮 OR 对应 h=1）。
*/

const int MAXN = (1 << 17) + 5;

unsigned int tree[4 * MAXN];
int len[MAXN];

void build(int p, int l, int r, int h) {
    if (l == r) {
        cin >> tree[p];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid, h - 1);
    build(p << 1 | 1, mid + 1, r, h - 1);
    tree[p] = (h & 1) ? (tree[p << 1] | tree[p << 1 | 1]) : (tree[p << 1] ^ tree[p << 1 | 1]);
}

void update(int p, int l, int r, int pos, unsigned int v, int h) {
    if (l == r) {
        tree[p] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(p << 1, l, mid, pos, v, h - 1);
    else update(p << 1 | 1, mid + 1, r, pos, v, h - 1);
    tree[p] = (h & 1) ? (tree[p << 1] | tree[p << 1 | 1]) : (tree[p << 1] ^ tree[p << 1 | 1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    int N = 1 << n;
    build(1, 1, N, n);
    for (int i = 0; i < m; i++) {
        int p;
        unsigned int b;
        cin >> p >> b;
        update(1, 1, N, p, b, n);
        cout << tree[1] << "\n";
    }
    return 0;
}