思路与算法

用迭代DFS得到进入序tin及子树结束tout，子树u就是[tin[u],tout[u]]。将进入序每512个位置分一块。块内维护各颜色出现次数，并在颜色位集中置出现颜色的位；以块为叶建立线段树，内部结点位集是两孩子位集OR。改一个位置时，旧颜色计数减1、减至0才清位；新颜色计数从0变1才置位。只需更新这两个颜色所在64位字的祖先聚合，不扫描全部位集。查询时扫描两端不足整块的至多1022个位置，把范围内颜色置入临时位集；中间整块区间在线段树上拆成O(log块数)个标准结点，将其颜色范围对应的64位字OR进临时位集，首尾字再用掩码截去界外颜色，最后popcount得到不同颜色数。每条操作读取后立即按上次查询答案XOR解码再处理。

正确性说明

DFS进入序的子树连续性使所有查询恰为一个位置区间。一个块颜色位为1当且仅当该块至少一个位置有此颜色，计数过0时更新保证这一不变式；线段树按OR合并，归纳得到每个结点代表块并集的确切颜色集合。查询把整个位置范围拆成两端残块和不相交整块标准结点，二者覆盖完整且无遗漏，位OR自然去除多次出现的同一颜色。颜色范围掩码只保留[l,r]，popcount因此等于所求。更新仅改变旧/新颜色的出现性，其他位无需重算。XOR解码使用最近一次真实查询结果，故满足强制在线要求，未预先使用未来查询答案。

复杂度

令B=512，C=ceil(n/B)，K为不小于C的2次幂，W=ceil(n/64)。建树DFS及读入O(n)，位集初始化和聚合O(KW)。块内unordered_map计数期望初始化O(n)、最坏O(nB)；一次更新期望O(log K)，以哈希桶线性最坏界计O(B+log K)。一次查询O(B+W_l_r log K)，其中W_l_r是颜色查询范围涉及的64位字数，不超过W；清空临时字和popcount都已包含。总空间O(n+KW)，不是给每个原树结点保存完整n位颜色集合。满n=q100000混合强制在线沙箱实测通过原3秒限制。

易错点

同块同色有多个位置时，删除其中一个不能清除该颜色位。旧、新颜色落在同一个64位字也需得到最终正确OR值。只XOR操作码之后的参数，lastans只有询问后变化。颜色63/64/65及首末掩码、单点树和不足整块尾部都要处理。查询颜色区间按字面取交集，可先截到[1,n]；截后为空直接输出0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int B = 512;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q, t;
    cin >> n >> q >> t;
    vector<int> color(n), tin(n), tout(n), order;
    for (int &c : color)
        cin >> c;
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> par(n, -1), iter(n), st(1, 0);
    while (!st.empty()) {
        int u = st.back();
        if (!iter[u]) {
            tin[u] = order.size();
            order.push_back(u);
        }
        if (iter[u] < (int)g[u].size()) {
            int v = g[u][iter[u]++];
            if (v != par[u]) {
                par[v] = u;
                st.push_back(v);
            }
        } else {
            tout[u] = order.size() - 1;
            st.pop_back();
        }
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        a[tin[i]] = color[i];
    int blocks = (n + B - 1) / B, K = 1, W = (n + 63) / 64;
    while (K < blocks)
        K *= 2;
    vector<unsigned long long> bits((size_t)2 * K * W), buf(W);
    vector<unordered_map<int, int>> cnt(blocks);
    for (auto &m : cnt)
        m.reserve(B * 2);
    for (int i = 0; i < n; i++) {
        int b = i / B, c = a[i] - 1;
        cnt[b][c]++;
        bits[(size_t)(K + b) * W + c / 64] |= 1ull << (c % 64);
    }
    for (int u = K - 1; u; u--)
        for (int j = 0; j < W; j++)
            bits[(size_t)u * W + j] =
                bits[(size_t)(u * 2) * W + j] | bits[(size_t)(u * 2 + 1) * W + j];
    auto pullword = [&](int block, int word) {
        for (int u = (K + block) / 2; u; u /= 2)
            bits[(size_t)u * W + word] =
                bits[(size_t)(u * 2) * W + word] | bits[(size_t)(u * 2 + 1) * W + word];
    };
    int last = 0;
    while (q--) {
        int op;
        long long u;
        cin >> op >> u;
        if (t)
            u ^= last;
        --u;
        if (op == 2) {
            long long value;
            cin >> value;
            if (t)
                value ^= last;
            int pos = tin[u], b = pos / B, old = a[pos] - 1, c = (int)value - 1;
            if (old == c)
                continue;
            if (--cnt[b][old] == 0) {
                cnt[b].erase(old);
                bits[(size_t)(K + b) * W + old / 64] &= ~(1ull << (old % 64));
                pullword(b, old / 64);
            }
            if (cnt[b][c]++ == 0) {
                bits[(size_t)(K + b) * W + c / 64] |= 1ull << (c % 64);
                pullword(b, c / 64);
            }
            a[pos] = c + 1;
        } else {
            long long ll, rr;
            cin >> ll >> rr;
            if (t) {
                ll ^= last;
                rr ^= last;
            }
            ll = max(ll, 1ll);
            rr = min(rr, (long long)n);
            if (ll > rr) {
                last = 0;
                cout << 0 << '\n';
                continue;
            }
            int lc = ll - 1, rc = rr - 1, wl = lc / 64, wr = rc / 64;
            fill(buf.begin() + wl, buf.begin() + wr + 1, 0);
            int L = tin[u], R = tout[u];
            auto add = [&](int p) {
                int c = a[p] - 1;
                if (lc <= c && c <= rc)
                    buf[c / 64] |= 1ull << (c % 64);
            };
            while (L <= R && L % B)
                add(L++);
            while (L <= R && (R + 1) % B)
                add(R--);
            if (L <= R) {
                int l = L / B + K, r = (R + 1) / B + K;
                int nodes[32], z = 0;
                while (l < r) {
                    if (l & 1)
                        nodes[z++] = l++;
                    if (r & 1)
                        nodes[z++] = --r;
                    l /= 2;
                    r /= 2;
                }
                for (int j = 0; j < z; j++) {
                    auto base = (size_t)nodes[j] * W;
                    for (int w = wl; w <= wr; w++)
                        buf[w] |= bits[base + w];
                }
            }
            buf[wl] &= (~0ull) << (lc % 64);
            buf[wr] &= (~0ull) >> (63 - rc % 64);
            last = 0;
            for (int w = wl; w <= wr; w++)
                last += __builtin_popcountll(buf[w]);
            cout << last << '\n';
        }
    }
}