-
交叉的线段之间的边是双向边，可以用并查集维护。
由于线段长度严格单调递增，只会出现后面的线段包含前面的线段的情况，因此直接用线段树去连边，并查集的正确性可以保证。
对于包含的线段，由于 \(a\in b, b\in c \longrightarrow a\in c\) ，这种单向边最多只走一条，直接最后 \(check\) 一下即可。
时间复杂度 \(\mathrm{O(n \alpha n\log n)}\) 。
-
\(\texttt{CF526F Pudding Monsters}\)
由于每行每列只有一个点，可以将所有的 \((x,y)\) 映射成一个排列 \(p[x]=y\) ，那么一个大小为 \(k\) 的合法子矩阵满足：
\[\max - \min + 1 = k \]考虑计算每个 \(r\) 的贡献，则合法的 \(l\) 满足 \(\max - \min + l = r\)，由于 \([r,r]\) 必然合法，并且 \(\max - \min + l \ge r\)，则有贡献的 \(l\) 满足
\[\max - \min + l = \min\limits_{i=1}^{r}(\max - \min + i) \]用线段树维护区间最小值的个数即可，时间复杂度 \(\mathrm{O(n\log n)}\) 。
-
\(\texttt{CF453E Little Pony and Lord Tirek}\)
将每个位置最近一次被查询的时间记作该位置的颜色，则每次查询最多只会使得序列颜色段数 \(+2\)，并且每查询一段就会使整个序列的颜色段数 \(-1\)，均摊下来查询的颜色段数是 \(O(1)\) 的，可以直接暴力。
考虑一个颜色段怎么做，对于每只