Codeforces 339D-Xenia and Bit Operations(线段树)

传送门

• 还是比较明显的线段树的操作

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

const int N = 2e6 + 10;
int a[N];
int tn, m, n;

struct stree
{
    int id, num;

} tree[N << 2];

int ls(int x) { return x << 1; }
int rs(int x) { return x << 1 | 1; }

void pushup(int rt)
{
    tree[rt].id = tree[ls(rt)].id ^ 1;
    if (tree[rt].id == 1)
    {
        tree[rt].num = tree[ls(rt)].num | tree[rs(rt)].num;
        return;
    }
    else
    {
        tree[rt].num = tree[ls(rt)].num ^ tree[rs(rt)].num;
    }
}

void build(int rt, int l, int r)
{
    if (l == r)
    {
        tree[rt].num = a[l];
        tree[rt].id = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(ls(rt), l, mid);
    build(rs(rt), mid + 1, r);
    pushup(rt);
}

void update(int rt, int Id, int num, int l, int r)
{
    if (l == r && l == Id)
    {
        tree[rt].num = num;
        return;
    }
    int mid = (l + r) / 2;
    if (Id <= mid)
        update(ls(rt), Id, num, l, mid);
    else
        update(rs(rt), Id, num, mid + 1, r);
    pushup(rt);
}

int queryFirst(int rt)
{
    return tree[rt].num;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> tn >> m;
    n = pow(2, tn);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    build(1, 1, n);
    for (int i = 0; i < m; ++i)
    {
        int p, b;
        cin >> p >> b;
        a[p] = b;
        update(1, p, b, 1, n);
        cout << queryFirst(1) << "
";
    }
    return 0;
}