题解 CF2165F Arctic Acquisition

· · 题解

题解 CF2165F Arctic Acquisition

其他题

感谢出题人解答了我的一些弱智问题。

题意

定义一个序列为锯齿状的，当且仅当其存在一个长度为 5 的子序列 a' 使得该子序列的元素按大小升序排序后是 a'_2,a'_1,a'_4,a'_3,a'_5。

给定一个长度为 n 的排列 p，求其有多少个子区间是锯齿状的。

数据范围：多测，\sum n\le10^6，值域 [1,n]。

做法

谁家好人线段树题开 10^6 啊？？？？？

我**的做了 2h 没做出来看眼提示让我扫描线，直接天塌了。只能说过于菜，没一眼秒掉，一旦开始长考基本上就倒闭了。

锯齿状的五个点画出来大约是这样的：

下面说的“第 k 个点”就是上图中从左往右的第 k 个。

首先容易想到的是枚举左端点并求出最靠左的右端点，然后拿这些极小的区间求所有不合法的情况（即包含它们中的任意一个就爆了）。

一旦左端点定了那首先第二个点肯定选右边第一个比它小的，因为从图中可以看出来第二个点的值对后面的点不构成限制（因为第一个点的值更大），但下标是有限制的，所以一定是越靠左越好。这个搞棵权值线段树倒着扫一下预处理出来就行。

接下来对后三个点的考虑还是十分常规地当成整体。此时我们对后三个点的限制就是第四个点要大于第一个点且第三个点要在第二个点后面，于是考虑维护所有“第三个点”“第四个点”能找到的最小“第五个点”，那原问题就变成一个二维数点了。

但直接维护所有的情况是 n^2 的显然不行，所以考虑只维护极小的，即不存在将其从第三个点的下标、第五个点的下标、第四个点的值三维偏序的其他子区间。这时有结论：每个“第四个点”所对应的最优“第五个点”必然是当前“第四个点”后第一个值比其大的。

题解里那个图是拿来证明的，而且前两种情况一眼可以合并。考虑用一个值在“第四个点”以上、值在“第四个点”“第五个点”之间的点来更新现有的后三个点。

综上结论是正确的。

证明了结论正确后就可以同样用线段树解决问题了。复杂度就是线段树的复杂度即 O(n\log n)。