思路与算法

对每位把一段与非操作压缩成输入0和输入1时的输出二元组(z,o)。恒等为(0,mask)，单节点w为(mask,~w&mask)。按函数复合合并，线段树同时保存正向和反向；树链剖分按路径方向拼接，初始输入0的结果为最终z。点修改重建沿途函数。

正确性说明

每位独立且输入只有两种，二元组完整描述段函数。复合准确模拟依次操作，具有结合性；树链剖分将路径分成有序且不重复的段，反向函数保证方向一致，因此最终与逐节点折叠等价。

复杂度

初始化建树与线段树O(N)，点修改O(logN)，路径查询O(log²N)，总O(N+Mlog²N)时间，O(N)空间。

易错点

与非不交换，不能任意交换段次序。K=32使用全32位掩码，避免1<<32。公开样例同点查询合法，包内已说明，节点只计算一次。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct HLD {
    int n;
    vector<vector<int>> g;
    vector<int> p, dep, sz, heavy, top, id, rev, ord;
    HLD(int n) : n(n), g(n), p(n, -1), dep(n), sz(n, 1), heavy(n, -1), top(n), id(n), rev(n) {
    }
    void build() {
        ord = {0};
        for (size_t i = 0; i < ord.size(); i++) {
            int u = ord[i];
            for (int v : g[u])
                if (v != p[u]) {
                    p[v] = u;
                    dep[v] = dep[u] + 1;
                    ord.push_back(v);
                }
        }
        for (int i = n - 1; i > 0; i--) {
            int u = ord[i], v = p[u];
            sz[v] += sz[u];
            if (heavy[v] < 0 || sz[u] > sz[heavy[v]])
                heavy[v] = u;
        }
        int timer = 0;
        vector<pair<int, int>> st(1, {0, 0});
        while (!st.empty()) {
            auto x = st.back();
            st.pop_back();
            for (int u = x.first; u >= 0; u = heavy[u]) {
                top[u] = x.second;
                id[u] = timer;
                rev[timer++] = u;
                for (int v : g[u])
                    if (v != p[u] && v != heavy[u])
                        st.push_back({v, v});
            }
        }
    }
    vector<array<int, 3>> path(int a, int b) {
        vector<array<int, 3>> L, R;
        while (top[a] != top[b]) {
            if (dep[top[a]] >= dep[top[b]]) {
                L.push_back({id[top[a]], id[a], 0});
                a = p[top[a]];
            } else {
                R.push_back({id[top[b]], id[b], 1});
                b = p[top[b]];
            }
        }
        if (dep[a] >= dep[b])
            L.push_back({id[b], id[a], 0});
        else
            L.push_back({id[a], id[b], 1});
        reverse(R.begin(), R.end());
        L.insert(L.end(), R.begin(), R.end());
        return L;
    }
};
struct Fun {
    uint32_t z, o;
};
Fun compose(Fun a, Fun b) {
    return {(b.z & ~a.z) | (b.o & a.z), (b.z & ~a.o) | (b.o & a.o)};
}
struct Seg {
    int n;
    uint32_t mask;
    vector<Fun> f, r;
    Seg(vector<uint32_t> &a, uint32_t m) : n(a.size()), mask(m), f(4 * n), r(4 * n) {
        build(1, 0, n - 1, a);
    }
    void pull(int v) {
        f[v] = compose(f[v * 2], f[v * 2 + 1]);
        r[v] = compose(r[v * 2 + 1], r[v * 2]);
    }
    void build(int v, int l, int rr, vector<uint32_t> &a) {
        if (l == rr) {
            f[v] = r[v] = {mask, (~a[l]) & mask};
            return;
        }
        int m = (l + rr) / 2;
        build(v * 2, l, m, a);
        build(v * 2 + 1, m + 1, rr, a);
        pull(v);
    }
    void change(int v, int l, int rr, int p, uint32_t w) {
        if (l == rr) {
            f[v] = r[v] = {mask, (~w) & mask};
            return;
        }
        int m = (l + rr) / 2;
        if (p <= m)
            change(v * 2, l, m, p, w);
        else
            change(v * 2 + 1, m + 1, rr, p, w);
        pull(v);
    }
    Fun query(int v, int l, int rr, int a, int b, bool forward) {
        if (a <= l && rr <= b)
            return forward ? f[v] : r[v];
        int m = (l + rr) / 2;
        if (b <= m)
            return query(v * 2, l, m, a, b, forward);
        if (a > m)
            return query(v * 2 + 1, m + 1, rr, a, b, forward);
        auto x = query(v * 2, l, m, a, b, forward), y = query(v * 2 + 1, m + 1, rr, a, b, forward);
        return forward ? compose(x, y) : compose(y, x);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    uint32_t mask = k == 32 ? UINT32_MAX : (1U << k) - 1;
    vector<uint32_t> w(n);
    for (auto &x : w) {
        unsigned long long y;
        cin >> y;
        x = y;
    }
    HLD h(n);
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        h.g[--a].push_back(--b);
        h.g[b].push_back(a);
    }
    h.build();
    vector<uint32_t> a(n);
    for (int u = 0; u < n; u++)
        a[h.id[u]] = w[u];
    Seg seg(a, mask);
    while (m--) {
        string op;
        int x;
        unsigned long long y;
        cin >> op >> x >> y;
        --x;
        if (op == "Replace")
            seg.change(1, 0, n - 1, h.id[x], (uint32_t)y);
        else {
            Fun f{0, mask};
            for (auto q : h.path(x, (int)y - 1))
                f = compose(f, seg.query(1, 0, n - 1, q[0], q[1], q[2]));
            cout << (unsigned long long)f.z << '\n';
        }
    }
}