CF911G Mass Change Queries

题解

首先这题有一个很一眼的分块做法，并且由于只需要维护颜色，所以会极其好写。
对每个块维护并查集，表示整块中颜色变成了哪个颜色，每个位置单独也指向一个颜色表示最初指向哪个颜色，这样就很好维护了。

但是发现值最大只有 \(100\)，所以考虑和值相关的做法。

有两种做法，挺不错的。

第一种做法比较暴力，对线段树每一个节点维护 \(100\) 个 \(tag\) 就行了，常数巨大。

第二种做法很有意思。
对每个值都开一颗线段树，表示某一个位置上面有没有。
然后修改就是取出 \(x\) 中 \(l\) 到 \(r\) 的节点，合并到 \(y\) 相同值域的位置上去，然后再删掉 \(x\) 上相对应的节点。
也就是说其实线段树单独的一个节点也是能合并的，跑得很快。