本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-08 16:31:27

考虑到最后拼接成的值域区间是连续的。我们维护拼接出这段区间需要几个原序列中的区间。

考虑固定值域右端点 $r$，维护 $[l, r]$ 在原序列中的段数。考虑加入一个数，如果原序列中和他相邻的数还没有被加入，那么它是不会相邻的，序列段数全都加一。

如果和它相邻的某一个已经加入了，那么段数和原来一样。特别地，如果它的左右两边都已经被加入了，那么段数还要减去一。

我们每次数的就是以它为右端点，左边为 $1$ 或者 $2$ 的数的数量。考虑到每个数都是正的，那么 $1$ 或者 $2$ 一定是最小值或者次小值。于是我们做一个最小值 / 次小值计数就好了。线段树维护完了。