CF452F Permutation

题目链接：CF452F

给你一个1到n的排列，你需要判断该排列内部是否存在一个3个元素的子序列(可以不连续)，使得这个子序列是等差序列。

n\leq 3\times 10^5。

Tutorial

不妨设 g[x] 为 x 的位置。题即求是否存在 g_{x-t} < g_x < g_{x+t}g_{x-t} > g_x > g_{x+t}

若从小到大枚举 i，其余 g 根据 g_{p_i} 大小关系赋为 0/1。则对于每个 x 判断是否存在 t 满足 g_{x-t} \not = g_{x+t}。

相当于从 x 出发两侧的 g 完全相等，哈希并用线段树维护即可。

时间复杂度：O(N\log N)。

Solution