线段树维护哈希

显然两个区间的哈希值是可以合并的，所以线段树可以维护区间的哈希值。

设左儿子的长度和哈希值分别为 \(sz_a,h_a\)，右儿子的长度和哈希值分别为 \(sz_b,h_b\)，合并后的长度为 \(sz_a + sz_b\)，哈希值为 \(h_a \times base^{sz_b} + h_b\)。

1. CF213E Two Permutations

枚举 \(b\) 的值区间 \([x,x+n-1]\)，令 \(pos_{b_x} = x\)，那么我们需要判断 \([b_{pos_{x-n+1}},b_{pos_x}]\) 在原排列里构成的子序列的哈希值是否与排列 \(a\) 整体加 \(x-1\) 的哈希值相等。类似滑动窗口，每次添加、删除一个数，然后维护整个序列的哈希值即可。

2. CF452F Permutation & P2757 [国家集训队]等差子序列

判断序列里是否存在一个子序列是三元等差数列，可以枚举中间项 \(b\)，如果存在公差 \(k\) 使得 \(b-k,b+k\) 在序列中出现在 \(b\) 的异侧就是 YES，否则就是 NO。但是直接枚举 \(b,k\) 是 \(O(n^2)\) 的。

可以考虑优化掉枚举公差 \(k\) 的过程。从小到大枚举 \(b\)，维护一个 01 串表示 \(x\) 是否出现过，那么如果串不是回文的就表示存在一个 \(k\) 满足 \(x-k\) 出现过而 \(x+k\) 没出现过，符合判定条件。于是直接线段树维护即可。

原文地址：http://www.cnblogs.com/zltzlt-blog/p/16797435.html