CF1638E Colorful Operations 笔记

由于加操作是对全局的指定颜色，不涉及区间形式，因此不考虑使用线段树等数据结构“寻找”到这个颜色再进行区间修改。

如果没有修改颜色的操作，每个位置有初始值 $a_i$，显然使用一个 ${\mathrm{tag}}_{\mathrm{c}}$ 记录所有对颜色 $c$ 的操作，那么位置 $i$ 的最终答案就是 $a_i+{\mathrm{tag}}_{c_i}$。

现在考虑颜色修改 $c\to c^{\prime }$，如果是单点修改 $i$，那么应该把 $a_i+{\mathrm{tag}}_c-{\mathrm{tag}}_{c^{\prime }}\to a_i^{\prime }$。

接着到区间修改，考虑一个小优化：对于旧颜色相同的一段区间，他们要进行的覆盖颜色和加 ${\mathrm{tag}}_c$ 的操作相同，可以用线段树打标记的方式解决。

再分析一下发现复杂度是正确的：每次区间覆盖会创造 $\log n$ 个线段树上颜色相同的线段，而每个线段只会被删除一次，因此时间复杂度 $O(q\log n)$，空间复杂度 $O(n)$。