Coloring Roads

重链剖分 + 颜色段均摊，维护每种颜色 $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)$。