CF竞赛题目讲解_CF452F(线段树+hash)

// https://codeforces.com/problemset/problem/452/F

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

// a1,x,a2 是等差数列，则 a1,a2 关于x对称。

// 所以出现在x之前的数据关于x对称，则不存在3个数的等差数列以x为中间项；如果出现在x之前的数据关于x不对称，则存在3个数的等差数列。

// 例如：1，5，3，2，4，出现在3之前的数据1，5关于3对称，则不存在3个数的等差数列1，3，5以3为中间项；

// 1，3，2，4，5，出现在3之前的数据1关于3不对称，则存在3个数的等差数列1，3，5。

// 思路类似于下题

// https://codeforces.com/contest/213/problem/E

//  线段树+hash

// 首先我们可以知道A序列是1~n的排列，那么我们可以先在B序列中把1~n的排列找出来，看其相对位置是否与A相同(hash可做)，相同即表明存在一个d=0满足条件。

// 以此类推，我们接下来可以把B中 2~ n + 1的排列找出来，如果其每位-1后相对顺序还是与A序列一致，即存在d=1也满足。。。

// 线段树中保存一个长度为n的序列的hash。

// hash函数值：  a[1]*23^(n-1) + a[2]*23^(n-2) + a[3]*23^(n-3)+  ......   

// 另一个线段树例子：CF竞赛题目讲解_CF213E(线段树+hash)

// https://www.bilibili.com/video/BV1KB4y1Q79G?spm_id_from=333.999.0.0