CF193D Two Segments

__ryp__ · 2024-10-08 16:31:27 · 个人记录

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

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

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

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