思路

一次位置可能被染色很多次，但最终只保留编号最大的那次操作。于是可以把操作顺序倒过来：第一次遇到某个位置时，当前操作就是它的最终颜色；之后不必再访问这个位置。

为了快速跳过已经确定颜色的位置，维护每个位置右侧第一个尚未确定颜色的位置。一个位置被写入答案后，把它与下一个位置连接起来。

做法

从 $i=m$ 到 $1$ 依次计算本次操作的两个端点，并令较小者为左端点、较大者为右端点。

查询左端点开始的第一个未染位置。若它不超过右端点，就把答案设为 $i$，再把这个位置连接到右侧第一个未染位置，继续查询。由于操作按倒序处理，已经赋值的位置绝不会被改写。

可以增加一个编号为 $n+1$ 的哨兵，表示右侧已经没有未染位置。

第一档限制可直接按正序枚举每次操作覆盖的全部位置。第二档限制可用支持区间覆盖标记的线段树按正序完成每次赋值，最后下传标记并输出叶子答案。

正确性证明

对任意位置 $x$，设覆盖它的操作中编号最大者为 $j$。倒序处理时，在操作 $j$ 之前只处理了编号更大的操作，而它们都不覆盖 $x$，所以 $x$ 尚未确定颜色。处理操作 $j$ 时，跳跃并查集一定会访问到 $x$，并把它的颜色设为 $j$。

此后只会处理编号小于 $j$ 的操作。位置 $x$ 已经从未染位置集合中删除，因此不会再次被访问或改写。于是 $x$ 的最终颜色恰为正序染色后的最后一次覆盖颜色。若不存在覆盖 $x$ 的操作，它始终没有被访问，答案保持为 $0$。

上述论证对每个位置都成立，因此算法输出全部雪花的正确最终颜色。

复杂度

每次操作只做常数次端点计算，每个位置至多被赋值并删除一次。时间复杂度为 $O((n+m)\alpha(n))$，空间复杂度为 $O(n)$。