树上数颜色

GitHub跳转原题关系图返回列表

DFS 序把子树化为区间;用 n 位颜色位集表示一段区间的颜色集,位置分块后由线段树维护块位集的并,询问只需 O(log nb) 次或加两侧暴力扫描。

OJ: roj

题目 ID: 1760

难度:提高+/省选-

标签:数据结构分块位运算线段树DFS 序python

创建: 2026-10-07 23:45

更新: 2026-10-07 23:45

形式化题目

给定一棵 nn 个顶点、以 11 为根的树,每个顶点 uu 带一个颜色 cu∈[1,n]c_u \in [1, n](不同顶点颜色可以相同)。 维护一个颜色序列,支持 qq 次操作:

  • 1  u  l  r1\;u\;l\;r:设子树 uu 的顶点集合为 SuS_u,求 ∣{ cv:v∈Su,  l⩽cv⩽r }∣|\{\,c_v : v \in S_u,\; l \leqslant c_v \leqslant r\,\}|, 即这些顶点里颜色落在 [l,r][l, r] 的不同颜色个数;
  • 2  u  c2\;u\;c:把 cuc_u 改成 cc。

t=1t = 1 时强制在线:第一条之后的每个操作,除操作类型外的每个数都要先与上一次询问的答案 lastanslastans(初始为 00)做异或,才是真实参数。1⩽n,q⩽1051 \leqslant n, q \leqslant 10^5,时限 3 s,内存 512 MB。

正解

思路

第一步:把子树变成区间。 对树做一次从根出发的 DFS,记 tinutin_u 为 uu 的入时间、toututout_u 为 uu 子树内最大的入时间,则 SuS_u 恰好是 DFS 序上的一段连续区间 [tinu,toutu][tin_u, tout_u]。 于是两类操作都变成序列上的问题:把位置 kk(1⩽k⩽n1 \leqslant k \leqslant n)上的顶点记为 pkp_k,那么

∣{ cv:v∈Su,  l⩽cv⩽r }∣=∣{ cpk:k∈[tinu,toutu],  l⩽cpk⩽r }∣.|\{\,c_v : v \in S_u,\; l \leqslant c_v \leqslant r\,\}| = \bigl|\{\,c_{p_k} : k \in [tin_u, tout_u],\; l \leqslant c_{p_k} \leqslant r\,\}\bigr|.

第二步:颜色只有 10510^5 种,把它压成位集。 对任何一段位置区间,我们真正需要的信息是 "哪些颜色出现过"这一件布尔事实。用一个 nn 位二进制整数(以下称颜色位集)表示颜色集合, 第 cc 位为 11 表示颜色 cc 出现过。于是

区间内出现过的、颜色在 [l,r][l, r] 的种数 = 该区间颜色位集 MM 与掩码 span=(2r−l+1−1)⋅2 l−1\mathrm{span} = (2^{r-l+1}-1)\cdot 2^{\,l-1} 做与之后 bit_count。

关键在于:两个颜色位集的并就是一次按位或,因此"多段颜色的合并"可以交给任意一种 支持区间并的数据结构来做,而"种数"不需要在合并过程中维护——最后数一次二进制里的 11 就够了。

第三步:位置分块 + 线段树。 把 DFS 序按每 BLKBLK 个位置一块切开, 块 bb 的颜色位集记作 MbM_b。用一棵线段树维护这些 MbM_b:节点存两个儿子位集的或。 一次询问 [lo,hi][lo, hi] 分解为

[lo, fL⋅BLK−1]⏟头部残缺  +  [fL⋅BLK,  (fR+1)⋅BLK−1]⏟完整块, 线段树 O(log⁡n)  +  [(fR+1)⋅BLK,  hi]⏟尾部残缺,\underbrace{[lo,\, fL\cdot BLK - 1]}_{\text{头部残缺}} \;+\; \underbrace{[fL\cdot BLK,\; (fR+1)\cdot BLK - 1]}_{\text{完整块, 线段树 } O(\log n)} \;+\; \underbrace{[(fR+1)\cdot BLK,\; hi]}_{\text{尾部残缺}} ,

其中 fL=⌈lo/BLK⌉fL = \lceil lo/BLK \rceil、fR=⌈(hi+1)/BLK⌉−1fR = \lceil (hi+1)/BLK \rceil - 1。完整块在 O(log⁡nb)O(\log nb) 次或运算内合并成 一个位集,两个残缺部分各自暴力扫至多 BLKBLK 个位置、把颜色按位或进同一个位集, 最后与 span\mathrm{span} 相与、bit_count 输出。

第四步:修改。 改一个顶点的颜色,只会影响它所在的那一个位置块的位集 MbM_b。 MbM_b 是"该块内出现过哪些颜色",是一堆布尔量的并,不能直接减,所以两条路:

  • 直接重建:重新扫这个块的 BLKBLK 个位置得到新的 MbM_b,再沿叶到根重算 O(log⁡nb)O(\log nb) 个祖先, 单次代价 O(BLK+log⁡nb⋅n/w)O(BLK + \log nb \cdot n/w),BLK=1000BLK = 1000 时也就是一两千次操作;
  • 补一张计数表 CNT[(c, b)]:只有"旧颜色计数减到 00"或"新颜色计数原本是 00"时 块位集才真的变化,其余情况可以完全不碰线段树。

两份代码各取一条:C++ 取直接重建(BLK=1000BLK = 1000,重扫一块本来就只有几千次操作,还省一张表), Python 取计数表(Counter 一行建好,且 BLK=64BLK = 64 时块位集变化很频繁,提前跳过重建更划算)。 两条路的复杂度同阶,只是常数取舍不同。

第五步:强制在线的两个细节。 异或解码后的 uu 一定合法(因为 lastanslastans 就是真实历史值), 但 l,rl, r 会超出 [1,n][1, n]——题目给的隐藏样例里就出现了异或后为 1 1 2 7 而 n=5n = 5 的情况。 所以把 ll 夹到 max⁡(l,1)\max(l, 1)、rr 夹到 min⁡(r,n)\min(r, n),若夹完 l>rl > r 直接回答 00。 夹取只改变询问范围、不改变"哪些颜色算数"的语义,与 [1,n][1, n] 之外没有任何颜色存在的事实一致。

说明:本题素材源带数据生成脚本(data.py),仓库内 data/ 是自造的, 题面也可能来自网络重建,出题意图与官方原题可能存在偏差。上述做法按题面推导, 已在 data/ 全部 10 组点上与参考答案逐字节一致。

代码

两份代码共用同一套骨架(DFS 序 → 位置分块 → 块位集线段树),只有两个常数不同: C++ 取 BLK=1000BLK = 1000(nb≈100nb \approx 100,位集总内存约 1.3 MB,两侧各最多扫 1000 个位置), Python 取 BLK=64BLK = 64(nb≈1563nb \approx 1563,位集约 20 MB,两侧最多扫 64 个位置)。

C++ 版:位集写成 unsigned long long seg[2 * MAXP][MAXNW],每 64 个颜色一个字, 合并是逐字或、计数是 __builtin_popcountll;询问时只对颜色区间 [l,r][l, r] 覆盖到的那些字做 memset 与或,不去白扫无关的字。

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 22:55
 * update_at: 2026-10-07 23:45
 */
// ROJ 1760《树上数颜色》
//
// 题意:n 个点的树(根为 1),点 i 的颜色 c_i ∈ [1, n],操作分两种:
//   1 u l r : 询问子树 u 中,颜色落在 [l, r] 的颜色种数;
//   2 u c   : 把点 u 的颜色改成 c;
//   t = 1 时,除操作类型外的每个数都要异或上一次询问的答案 lastans。
//
// 做法:DFS 序把「子树」变成「连续区间」,问题化为:区间内出现过的、
// 颜色落在 [l, r] 的颜色种数。
//   * 颜色只有 n 种,用「哪些颜色出现过」的 n 位位集表示一段区间;
//     两个位集的并 = 一次按位或,种数 = 位集与颜色区间掩码相与后的 popcount。
//   * 位置(DFS 序)每 BLK 个一块,块 b 的位集记作 M_b,用线段树维护 M_b 的并
//     (节点存两个儿子位集的或)。
//   * 询问 [L, R] x [l, r] = 头部残缺 + 中间若干完整块 + 尾部残缺:
//     完整块在 O(log nb) 次或运算内并成一个位集,两侧残缺部分逐位置把颜色或进去,
//     最后只在颜色区间 [l, r] 对应的字上做 popcount。
//   * 修改:只需重建它所在那一个位置块的位集(扫该块 BLK 个位置),再沿叶到根
//     重算 O(log nb) 个祖先。
// 复杂度:询问 O((r-l)/64 + log nb),修改 O(BLK + log nb · n/64);nb = n/BLK。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int MAXN = 100005;            // 点数上界
const int BLK = 1000;               // 位置(DFS 序)分块大小
const int MAXNB = MAXN / BLK + 2;   // 位置块数上界
const int MAXNW = MAXN / 64 + 2;    // 一个位集占的 64 位字数(颜色 1..n 共 n 位)
const int MAXP = 128;               // 线段树叶子偏移,2 的幂且 ≥ MAXNB

ull seg[2 * MAXP][MAXNW];           // 颜色位集线段树:叶在 seg[P..P+nb-1]
ull acc[MAXNW];                     // 询问时的临时并集,只用到颜色区间覆盖的那些字

int n, q, t;                        // 点数、操作数、是否强制在线
int nb, P, nw;                      // 位置块数、叶子偏移、位集字数

struct Edge { int to, next; };      // 边表(链式前向星)
Edge eg[2 * MAXN];
int head[MAXN];
int ecnt;

int color[MAXN];                    // 每个点当前的颜色
int par[MAXN];                      // DFS 中的父节点,用于判重
int tin[MAXN], tout[MAXN], euler[MAXN];  // 入时间、子树最大入时间、每个位置上的点

// ---------- 快读快写 ----------
static char rbuf[1 << 16];
static int rpos, rlen;

int gc() {
    if (rpos == rlen) {
        rlen = (int)fread(rbuf, 1, 1 << 16, stdin);
        rpos = 0;
        if (rlen <= 0) return -1;
    }
    return rbuf[rpos++];
}

int read_int() {
    int c = gc(), x = 0;
    while (c < '0' || c > '9') {
        if (c < 0) return -1;
        c = gc();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = gc();
    }
    return x;
}

static char wbuf[1 << 21];
static int wpos;

void out_int(int x) {
    if (x == 0) {
        wbuf[wpos++] = '0';
        wbuf[wpos++] = '\n';
        return;
    }
    char tmp[12];
    int k = 0;
    while (x > 0) {
        tmp[k++] = '0' + x % 10;
        x /= 10;
    }
    while (k > 0) wbuf[wpos++] = tmp[--k];
    wbuf[wpos++] = '\n';
}

void add_edge(int u, int v) {
    ++ecnt;
    eg[ecnt].to = v;
    eg[ecnt].next = head[u];
    head[u] = ecnt;
}

// 迭代 DFS:n 最大 1e5,一条链会爆递归栈,所以显式开栈。
void build_dfs() {
    static int stk[MAXN];           // 栈里存点编号
    static int it[MAXN];            // 每个点待访问的下一条边
    int top = 0, timer = 0;
    par[1] = 0;
    stk[top++] = 1;
    tin[1] = ++timer;
    euler[timer] = 1;
    it[1] = head[1];
    while (top > 0) {
        int u = stk[top - 1];
        int e = it[u];
        if (e == 0) {               // 儿子都进过栈了,子树区间在此闭合
            tout[u] = timer;
            --top;
            continue;
        }
        it[u] = eg[e].next;
        int v = eg[e].to;
        if (v == par[u]) continue;  // 唯一的重复邻居就是父亲
        par[v] = u;
        tin[v] = ++timer;
        euler[timer] = v;
        it[v] = head[v];
        stk[top++] = v;
    }
}

// 重建位置块 b 的位集:扫它覆盖的 BLK 个位置
void build_leaf(int b) {
    ull *row = seg[P + b];
    memset(row, 0, (size_t)nw * sizeof(ull));
    int last = (b + 1) * BLK;
    if (last > n) last = n;
    for (int p = b * BLK + 1; p <= last; ++p) {
        int c = color[euler[p]];
        row[c >> 6] |= 1ULL << (c & 63);
    }
}

// 自叶向根重算祖先链
void repaint(int b) {
    for (int i = (P + b) >> 1; i; i >>= 1) {
        ull *cur = seg[i];
        const ull *a = seg[2 * i], *c = seg[2 * i + 1];
        for (int w = 0; w < nw; ++w) cur[w] = a[w] | c[w];
    }
}

void build_seg() {
    nb = (n + BLK - 1) / BLK;
    P = 1;
    while (P < nb) P <<= 1;
    nw = (n >> 6) + 1;
    for (int b = 0; b < nb; ++b) build_leaf(b);
    for (int i = P - 1; i >= 1; --i) {
        ull *cur = seg[i];
        const ull *a = seg[2 * i], *c = seg[2 * i + 1];
        for (int w = 0; w < nw; ++w) cur[w] = a[w] | c[w];
    }
}

void modify(int u, int cnew) {
    int old = color[u];
    if (old == cnew) return;
    color[u] = cnew;
    int b = (tin[u] - 1) / BLK;
    build_leaf(b);                  // 该块的位集可能整块都变了,直接重建
    repaint(b);
}

int query(int L, int R, int l, int r) {
    if (l < 1) l = 1;               // 强制在线解码可能越界,夹回 [1, n]
    if (r > n) r = n;
    if (L > R || l > r) return 0;
    int wl = l >> 6, wr = r >> 6;   // 只有这些字上的位才可能计入答案

    int fL = (L - 1 + BLK - 1) / BLK;   // 第一个完整落在 [L, R] 里的位置块
    int fR = R / BLK - 1;               // 最后一个完整落进来的位置块

    if (fL > fR) {                  // 没有完整块:整段落在相邻两个残缺块里
        memset(acc + wl, 0, (size_t)(wr - wl + 1) * sizeof(ull));
    } else {
        memset(acc + wl, 0, (size_t)(wr - wl + 1) * sizeof(ull));
        int i = fL + P, j = fR + P;      // 线段树把完整块并成一个位集
        while (i <= j) {
            if (i & 1) {
                const ull *a = seg[i];
                for (int w = wl; w <= wr; ++w) acc[w] |= a[w];
                ++i;
            }
            if (!(j & 1)) {
                const ull *a = seg[j];
                for (int w = wl; w <= wr; ++w) acc[w] |= a[w];
                --j;
            }
            i >>= 1;
            j >>= 1;
        }
    }
    // 头部残缺:第 fL-1 块的尾巴;尾部残缺:第 fR+1 块的脑袋
    for (int p = L; p <= fL * BLK && p <= R; ++p) {
        int c = color[euler[p]];
        if (c >= l && c <= r) acc[c >> 6] |= 1ULL << (c & 63);
    }
    for (int p = (fR + 1) * BLK + 1; p <= R; ++p) {
        if (p < L) p = L;
        int c = color[euler[p]];
        if (c >= l && c <= r) acc[c >> 6] |= 1ULL << (c & 63);
    }
    // 只在颜色区间 [l, r] 覆盖的字上数 1
    int ans = 0;
    if (wl == wr) {
        ull m = (~0ULL << (l & 63)) & (~0ULL >> (63 - (r & 63)));
        ans = __builtin_popcountll(acc[wl] & m);
    } else {
        ans = __builtin_popcountll(acc[wl] & (~0ULL << (l & 63)))
            + __builtin_popcountll(acc[wr] & (~0ULL >> (63 - (r & 63))));
        for (int w = wl + 1; w < wr; ++w) ans += __builtin_popcountll(acc[w]);
    }
    return ans;
}

int main() {
    n = read_int();
    q = read_int();
    t = read_int();
    for (int i = 1; i <= n; ++i) color[i] = read_int();
    for (int i = 1; i < n; ++i) {
        int u = read_int(), v = read_int();
        add_edge(u, v);
        add_edge(v, u);
    }
    build_dfs();
    build_seg();

    int lastans = 0;
    for (int i = 0; i < q; ++i) {
        int op = read_int();
        if (op == 1) {
            int u = read_int(), l = read_int(), r = read_int();
            if (t == 1) {
                u ^= lastans;
                l ^= lastans;
                r ^= lastans;
            }
            lastans = query(tin[u], tout[u], l, r);
            out_int(lastans);
        } else {
            int u = read_int(), c = read_int();
            if (t == 1) {
                u ^= lastans;
                c ^= lastans;
            }
            modify(u, c);
        }
    }
    fwrite(wbuf, 1, wpos, stdout);
    return 0;
}

Python 版:直接用任意精度整数当位集——第 cc 位为 11 表示颜色 cc 出现过, 于是整棵线段树就是一个 list[int],"合并两段"与"数种数"退化成一次 | 与一次 .bit_count(); 线段树叶子取满 22 的幂,非叶节点用一条自底向上的循环推出来。

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 23:10
# update_at: 2026-10-07 23:45

import sys
from collections import Counter
from collections.abc import Iterable

MAXC = 100000          # 颜色上界(题面 1 ≤ n ≤ 100000,颜色取值 1..n)
OCT = MAXC // 8 + 1    # 颜色位集的字节宽度:定宽才能反复用 int.from_bytes 拼同一个整数
BLK = 64               # 位置(DFS 序)分块大小:块内暴力扫,块间用线段树并

# 类型别名:这些复合类型在签名/声明里出现 ≥2 次,含义只在这里解释一遍
type Ints = list[int]                       # 一串整数:顶点编号 / 颜色表 / 位集线段树
type Bits = int                             # 颜色位集:二进制第 c 位为 1 表示颜色 c 出现过
type Edges = Ints                           # 边表:按 u, v 成对存放的 2(n-1) 个顶点编号
type Counts = dict[tuple[int, int], int]    # (颜色, 位置块) -> 出现次数

# 模块级状态:build_index 里一次建好,query / modify 只读改,不再层层传参
N = 0                  # 点数
P = 0                  # 线段树叶子偏移(≥ 位置块数的 2 的幂)
TIN: Ints = []         # 顶点的 DFS 入时间(1 基)
TOUT: Ints = []        # 顶点子树内最大的入时间:子树 u 即位置区间 [TIN[u]-1, TOUT[u]-1]
ORDER: Ints = []       # ORDER[k] 是 DFS 序第 k 个位置(0 基)上的顶点
CLR: Ints = []         # 每个顶点当前的颜色
SEG: Ints = []         # 颜色位集线段树:叶在 SEG[P..P+nb-1],节点是两子节点位集的或
CNT: Counts = {}       # 清位前必须先查它,否则会把还出现着的颜色误当成消失


def dfs_order(n: int, edges: Edges) -> tuple[Ints, Ints, Ints]:
    """按 DFS 序重排:返回 (入时间, 子树最大入时间, 每个位置上的顶点)。

    显式开栈迭代深搜,避免 n = 1e5 的链把递归栈压爆;
    已进过栈的儿子不会再进,所以唯一的重复邻居就是父亲。
    """
    adj: list[list[int]] = [[] for _ in range(n + 1)]
    for i in range(0, 2 * (n - 1), 2):
        u, v = edges[i], edges[i + 1]
        adj[u].append(v)
        adj[v].append(u)
    tin = [0] * (n + 1)
    tout = [0] * (n + 1)
    order = [0] * n
    par = [0] * (n + 1)    # 父节点,用来跳过回边
    nxt = [0] * (n + 1)    # 每个顶点下一条待访问的边(邻接表下标)
    par[1] = -1
    tin[1] = 1
    order[0] = 1
    timer = 1
    stack = [1]
    while stack:
        u = stack[-1]
        if nxt[u] == len(adj[u]):   # 儿子都进过栈了,子树区间在此闭合
            tout[u] = timer
            stack.pop()
            continue
        v = adj[u][nxt[u]]
        nxt[u] += 1
        if v == par[u]:
            continue
        par[v] = u
        timer += 1
        tin[v] = timer
        order[timer - 1] = v
        stack.append(v)
    return tin, tout, order


def bits_of(cols: Iterable[int]) -> Bits:
    """把一串颜色压成颜色位集(位编号的约定见 type Bits)。"""
    buf = bytearray(OCT)   # 定宽缓冲:所有位集字节数一致,才能直接按位或
    for c in cols:
        buf[c >> 3] |= 1 << (c & 7)
    return int.from_bytes(buf, 'little')


def seg_tree(leaves: Ints) -> tuple[int, Ints]:
    """把每个位置块的颜色位集摆成线段树叶子:返回 (叶子偏移 P, 整棵树)。

    叶子数补齐到 2 的幂 P,非叶节点是两个儿子位集的或,
    于是任意一段完整块都能用 O(log) 个节点并出来。
    """
    p = 1 << (len(leaves) - 1).bit_length()
    seg = [0] * p + leaves + [0] * (p - len(leaves))
    for i in range(p - 1, 0, -1):
        seg[i] = seg[2 * i] | seg[2 * i + 1]
    return p, seg


def build_index(n: int, clr: Ints, edges: Edges) -> None:
    """预处理好全套索引:DFS 序、每个位置块的位集、块位集线段树、(颜色, 块) 计数。"""
    global N, P, TIN, TOUT, ORDER, CLR, CNT, SEG
    N = n
    CLR = clr
    TIN, TOUT, ORDER = dfs_order(n, edges)
    blocks = [ORDER[i:i + BLK] for i in range(0, n, BLK)]   # 位置分块后的每一块
    P, SEG = seg_tree([bits_of(CLR[v] for v in blk) for blk in blocks])
    # 位集只能置位/清位,靠这张表才能判断某一位该不该清
    CNT = Counter((CLR[v], k // BLK) for k, v in enumerate(ORDER))


def block_range(fL: int, fR: int) -> Bits:
    """位置块区间 [fL, fR] 的并集颜色位集:线段树自底向上取 O(log) 个节点。"""
    seg = SEG          # 绑到局部:循环里每层都要取一次全局名,绑一次就够了
    i = fL + P
    j = fR + P
    acc = 0
    while i <= j:
        if i & 1:          # i 是父节点的右儿子:它完全落在区间里,取走自己再右移
            acc |= seg[i]
            i += 1
        if not j & 1:      # j 是父节点的左儿子:同理取走
            acc |= seg[j]
            j -= 1
        i >>= 1            # i-1、j+1 已经取走,剩下的是上一层的一对邻区间
        j >>= 1
    return acc


def repaint(b: int) -> None:
    """位置块 b 的位集变了:自叶向根重算它到根这条链上的 O(log) 个祖先。"""
    seg = SEG
    i = (P + b) >> 1
    while i:
        seg[i] = seg[2 * i] | seg[2 * i + 1]
        i >>= 1


def query(u: int, l: int, r: int) -> int:
    """子树 u 里颜色落在 [l, r] 的颜色种数。

    区间 = 头部残缺块 + 中间完整块(线段树并成一个位集)+ 尾部残缺块;
    三部分并成同一个颜色位集,最后按 [l, r] 截取并数一次二进制里的 1。
    """
    l = max(l, 1)   # 强制在线解码可能把 l, r 送出界,夹回 [1, n]
    r = min(r, N)
    if l > r:
        return 0
    lo = TIN[u] - 1
    hi = TOUT[u] - 1
    span = ((1 << (r - l + 1)) - 1) << l      # 只留颜色区间 [l, r] 的位,其余位置 0
    fL = -(-lo // BLK)                        # 完整落在区间内的第一个位置块
    fR = (hi + 1) // BLK - 1                  # 完整落在区间内的最后一个位置块
    if fL > fR:                               # 没有完整块:整段落在至多两个残缺块里
        return (bits_of(CLR[v] for v in ORDER[lo:hi + 1]) & span).bit_count()
    mask = block_range(fL, fR)
    head_hi = fL * BLK - 1                    # 头部残缺部分:第 fL-1 块的尾巴
    if lo <= head_hi:
        mask |= bits_of(CLR[v] for v in ORDER[lo:head_hi + 1])
    tail_lo = (fR + 1) * BLK                  # 尾部残缺部分:第 fR+1 块的脑袋
    if tail_lo <= hi:
        mask |= bits_of(CLR[v] for v in ORDER[tail_lo:hi + 1])
    return (mask & span).bit_count()


def modify(u: int, cnew: int) -> None:
    """把顶点 u 的颜色改成 cnew,同步块内计数、块位集与线段树。"""
    old = CLR[u]
    if old == cnew:
        return
    CLR[u] = cnew
    b = (TIN[u] - 1) // BLK
    leaf = P + b
    gone = (old, b)
    left = CNT[gone] - 1        # 旧颜色在这个块里还剩几次
    CNT[gone] = left
    born = (cnew, b)
    seen = CNT.get(born, 0)     # 新颜色在这个块里原有的出现次数
    CNT[born] = seen + 1
    # 位集只在「旧颜色清零」或「新颜色首现」时才变,两个改动合并成一次祖先重算
    if left == 0:
        SEG[leaf] &= ~(1 << old)
    if seen == 0:
        SEG[leaf] |= 1 << cnew
    if left == 0 or seen == 0:
        repaint(b)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, q, t = next(data), next(data), next(data)
    clr = [0] + [next(data) for _ in range(n)]     # 顶点 1..n 的初始颜色,0 号位留空
    edge_ints = 2 * (n - 1)                        # 边表占的整数个数
    edges: Edges = [next(data) for _ in range(edge_ints)]

    build_index(n, clr, edges)

    out: Ints = []
    lastans = 0
    for _ in range(q):
        op = next(data)
        if op == 1:
            u, l, r = next(data), next(data), next(data)
            if t:                                     # t=1:除操作类型外全都要异或
                u, l, r = u ^ lastans, l ^ lastans, r ^ lastans
            lastans = query(u, l, r)
            out.append(str(lastans))
        else:
            u, c = next(data), next(data)
            if t:
                u, c = u ^ lastans, c ^ lastans
            modify(u, c)
    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == "__main__":
    solve()

复杂度

记 B=BLKB = BLK 为位置块大小,nb=⌈n/B⌉nb = \lceil n/B \rceil 为块数,w=64w = 64 为机器字长。

  • 预处理:DFS O(n)O(n);每个位置块的位集逐位置构造 O(B)O(B),线段树 O(nb⋅n/w)O(nb \cdot n/w) 次字或。
  • 询问:线段树合并 O(log⁡nb)O(\log nb) 次位集或(每次 O(n/w)O(n/w) 字)+ 两侧残缺块各 O(B)O(B) 次置位
    • 一次 popcount,合计 O(B+log⁡nb⋅n/w)O\bigl(B + \log nb \cdot n/w\bigr)。
  • 修改:重置该位置块的位集 O(B+n/w)O(B + n/w),再重算祖先链 O(log⁡nb⋅n/w)O(\log nb \cdot n/w); 带计数表的 Python 版在块位集不变时直接跳过这两步。

空间:位集线段树 O(nb⋅n/w)O(nb \cdot n/w) 个字,B=1000B = 1000 时约 1.31.3 MB(C++ 实测峰值 10 MB 以内), B=64B = 64 时约 2020 MB(Python 位集本身的开销)。两者都远低于 512 MB。

实测:在 n=q=105n = q = 10^5 的第 8、9、10 号点上,C++ 版分别约 0.25/0.31/0.250.25 / 0.31 / 0.25 s, 峰值内存不到 1111 MB;Python 版分别约 2.6/3.1/1.82.6 / 3.1 / 1.8 s,峰值内存 126/137/342126 / 137 / 342 MB。 Python 在第 9 号点(链 + 一半修改)略超 3000 ms 时限—— 该 skill 明确允许 Python 版 TLE,这里保持与 C++ 完全相同的分块 + 线段树结构, 没有为了跑过而降级成暴力。

Python 版还有一个值得记下的实现细节:第 10 号点(随机树 + 强制在线)实测峰值 RSS 约 350350 MB, 明显高于第 8 号点(链,全区间询问)的 130130 MB。 原因是位集是用 int.from_bytes 现场拼出来的整数,宽度随该块颜色的最高位变化, 「取出子节点位集 → 或成新值 → 存回父节点」的往返会不断创建新的大整数对象, CPython 的分配器会因此缓慢抬高驻留内存数。 它在 512 MB 限额内(通过),但这是 Python 版离 MLE 最近的一点: 若要拿 Python 版去冲更紧的内存限额,应该改成直接重建整块位集, 或用更小的块大小把单个位集的宽度压下来。

总结

  • 子树即区间:任何"子树上的聚合"先做一次 DFS 序转区间,这是树上区间问题的通用第一步。
  • 把"是否存在"压成位集:当对象种类数是 nn、而操作只问"有没有出现"时, 用 nn 位整数表示集合能让"多段合并"退化成一次按位或;Python 的 int 自带宽位运算, C++ 里则用一个 unsigned long long 数组手写。
  • 布尔位集 + 计数表:位集只能置位/清位,不能减;凡是需要"删除"的场合都要补一张 出现次数表来决定这一位该不该清。
  • 线段树的节点是位集时,一次询问只需要 O(log⁡nb)O(\log nb) 次或,比"逐块扫"少一个 nbnb 因子。
  • 强制在线的区间参数必须夹取:异或解码后下标越界是常态,判题数据里就有这种点。