题解：P12385 [蓝桥杯 2023 省 Python B] 异或和

LS_Z_66066 · 2025-05-02 21:15:48 · 题解

一道树状数组结合 dfs 序的简单应用。

题目要求点修区间查，考虑树状数组。

首先求出每个节点的 dfs 序，按照深搜的性质可得同一子树内的 dfs 序一定是连续的一段，即可把题目从树上问题转换成序列问题，之后就是单点修改和查询区间异或和。

Code：

#include <bits/stdc++.h>//
//#define Ri register int
//#define int long long
#define eb emplace_back
#define pb push_back

typedef long long ll;

inline int read(){
    int x = 0; bool f = 1;
    char ch = getchar();
    while(ch < 48 || ch > 57){
        if(ch == 45) f = 0;
        ch = getchar();
    }
    while(ch <= 57 && ch >= 48){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return f ? x : -x;
}

const int N = 1e5 + 3;

int n, m;

int a[N];

int dfn[N], tot, siz[N];

std :: vector<int> e[N];

inline void dfs(int u, int fath = 0) {
    dfn[u] = ++tot;
    siz[u] = 1;
    for(auto &v : e[u]) if(v ^ fath) {
        dfs(v, u);
        siz[u] += siz[v];
    }
}

int c[N];

inline void add(int x, int k) {
    for(; x <= n; x += (x & -x)) c[x] ^= k;
}

inline int qry(int x, int res = 0) {
    for(; x >= 1; x -= (x & -x)) res ^= c[x];
    return res;
}

signed main(){
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) a[i] = read();

    int op, x, y;
    for(int i = 1; i < n; ++i) x = read(), y = read(), e[x].eb(y), e[y].eb(x);

    dfs(1);

    for(int i = 1; i <= n; ++i) add(dfn[i], a[i]);

    while(m--) {
        op = read(), x = read();
        if(op & 1) {
            y = read();
            add(dfn[x], a[x]);
            add(dfn[x], a[x] = y);
        }
        else {
            std :: cout << (qry(dfn[x] + siz[x] - 1) ^ qry(dfn[x] - 1)) << "\n";
        }
    }

    return 0;
}

已更正格式。