CF193D

_acat_ · 2023-08-24 15:54:26 · 个人记录

题目大意：

给定一个 1 到 n 的排列，在这个排列中选出两端互不重叠的区间，求使选出的元素排序后构成公差为 1 的等差数列的方案数。

选出的两端区间中元素构成的集合相同时视为同一种方案， 1 \le n \le 3 \times 10^5。

分析：

考虑求个置换，假设原来的排列是 a，我们令 b_{a_i}=i，将会得到一个新的排列 b。

考虑原问题对于 b 而言相当于什么？

• 求有多少个区间，其中的数字是不超过两个的连续段。

考虑一个 n^2 暴力，枚举左端点 l，再枚举右端点 r，维护当前区间的连续段数量，每次将右端点元素加入当前区间。

那怎么维护连续段数量呢？

用一个 set 存储所有的元素，如果要新加一个元素 x，就在 set 中查找比 x 大的最小元素 y，和比 x 小的大元素 z。然后分类套路。

• 如果 y=x-1 并且 z=x-1，这意味着 x 合并了两个连续段，连续段数减一。
• 如果两个条件只满足一个，这意味着 x 融入了一个连续段，段数不变。
• 如果两个条件都不满足，这意味的 x 自己是一个新的连续段，段数加一。

怎么优化？

• 从小到大枚举 r，并且维护数组 f。f_i，表示以 i 为左端点的区间连续段数量。

随着 r 的枚举，f s数组会发生变化。

具体地说，当要插入 x 时，找到 x+1 在左边的位置 wz1，找到 x-1 在左边的位置 wz2。假设 wz1 小于 wz2，那么分类讨论 f 的变化：

是一个简单的区间操作，用线段树维护 f 即可，时间复杂度 O(n \log n)