ucup3-39-tokyo

A. Array Similarity

才过去三个月我已经退化到想不清楚也看不懂了……

对于一个区间 $[L,R]$，如果 $i\in [L,R]$ 并且 $a_i$ 可以成为区间里的前缀 $\max$，我们定义 $\ell_i\lt i$ 为其左侧第一个比他大的数，即 $a_{\ell_i}\ge a_i$，那么由于 $a_i= \max(a_L, \dots, a_{\ell_i})$，所以 $\ell_i\lt L$.

所以我们可以用位置的哈希之和来表示一整个区间。令 $p$ 是一个素数，在考虑用哈希的和表示区间 $[L,R]$ 时，用扫描线找出所有 $\ell_i\lt L\texttt{ and }i\in[L,R]$ 的位置 $i$ 并将 $p^i$ 加入树状数组，然后 $[L,R]$ 区间内的哈希和即为

算法就是先单调栈计算 $\ell_i$，然后对 $(\ell_i, i)$ 和 $[L,R]$ 分别排序，接着扫描线在 $[L,R]$ 上扫描，另一个指针判断 $\ell_i\lt L$ 并动态插入 $p^i$，用树状数组计算区间的哈希和（并除掉 $p^L$）；最后，判断 Query 的两个区间的哈希和是否相同. 时间复杂度 $O(n\log n)$.