显然两个区间的哈希值是可以合并的,所以线段树可以维护区间的哈希值。
设左儿子的长度和哈希值分别为 \(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\) 没出现过,符合判定条件。于是直接线段树维护即可。