Coloring Roads

lzyqwq · 2025-11-28 16:23:50 · 题解

重链剖分 + 颜色段均摊，维护每种颜色 v 出现次数 c_v 和每种出现次数 x 对应的颜色个数 \operatorname{cc}_x。插入、删除颜色段时两者的变化是好维护的。每次查询就是输出 \operatorname{cc}_m。

一共产生 \mathcal{O}(Q\log n) 个颜色段。认为 n,C,Q 同阶，时间复杂度 \mathcal{O}\left(Q\log^2 n\right)，空间复杂度 \mathcal{O}(n)。