题解 | #少男少女成双对#

F 题的稳定做法。代码参考：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=63558393

考虑到对于任意一个出现的数字，我们所选的区间都必须恰好包含 0 个或者 2 个这样的数字。接下来进行分析：

考虑数字 x，为了方便起见，我们钦定第 0 位和第 n + 1 位也是数字 x。

1. 区间 [l, r] 包含 0 个数字 x。那么考虑相邻的两个 x 出现的位置 ，我们有 。考虑去除 这一限制，我们发现这等价于限制 在一个矩形内。

2. 区间 [l, r] 包含 2 个数字 x。考虑相邻的四个 x 出现的位置 ，我们有 ，以及 。这也等价于一个矩形的限制。

不难发现，上述方案产生的所有矩形两两不交，所以可以同时对矩形覆盖到的地方加上 1。考虑总共有 个不同的数字 x，那么我们只需要统计满足 且位置 上的值恰好为 的点个数。

考虑根据 进行扫描线，在线段树上维护 位置对应的值。不难发现，每一个位置上的值不会超过 ，所以我们只需要在线段树上维护最大值和出现位置。由于前面在算矩形的时候去掉了 的限制，我们在此处需要通过仅查询后缀的形式将这个限制加上。

当然，如果对矩形的形成方式比较了解，也可以直接抛弃矩形思路，直接根据序列增量修改线段树。此处不再展开。