题解：P11659 小夫

考虑每一个 $a_y$ 位置对答案的贡献：

令 $cnt_{x,i}$ 表示前 $i$ 个数中 $x$ 出现的次数，$p1_{x,i}$ 为下标小于 $i$ 的第一个 $x$ 的下标。

假设询问区间为 $[L,R]$，令 $y=i$, $a_i=2p$ ，则 $a_i$ 对答案的贡献为 $( cnt_{4p,p1_{4p,i}} -cnt_{4p,p1_{4p,L}})(cnt_{3p,p1_{3p,R}}-cnt_{3p,p1_{3p,i}})$ , 展开可得: $cnt_{4p,p1_{4p,i}}cnt_{3p,p1_{3p,R}}-cnt_{3p,p1_{3p,i}}cnt_{4p,p1_{4p,i}}-cnt_{4p,p1_{4p,L}}cnt_{3p,p1_{3p,R}}+cnt_{4p,p1_{4p,L}}cnt_{3p,p1_{3p,i}}$ 。

对于区间范围内左侧没有 $a_x$ ,或右侧没有 $a_z$ 的 $a_i$，它们对答案没有贡献，直接去掉即可。假设去掉部分 $a_i$ 后剩下了 $num$ 个。

于是询问的答案 $Ans= cnt_{3p,p1_{3p,R}}\sum _ {i=L}^R cnt_{4p,p1_{4p,i}}-\sum _ {i=L}^R cnt_{3p,p1_{3p,i}}cnt_{4p,p1_{4p,i}}-num*cnt_{4p,p1_{4p,L}}cnt_{3p,p1_{3p,R}}+cnt_{4p,p1_{4p,L}} \sum _ {i=L}^R cnt_{3p,p1_{3p,i}}$ 。

其中 $cnt_{x,i}$ ， $\sum _ {i=L}^R cnt_{4p,p1_{4p,i}}$ ， $\sum _ {i=L}^R cnt_{3p,p1_{3p,i}}cnt_{4p,p1_{4p,i}}$ ， $\sum _ {i=L}^R cnt_{3p,p1_{3p,i}}$ 均可以使用前缀和维护, $num$ 可以在每次询问时二分求出。本题值域在 $2 \times 10^5$ 范围内，可以开 vector 数组直接存而无需离散化。

均摊下来，时间复杂度 $O(n+m logn)$ ，空间复杂度 $O(n)$。

这样就做完了，并不需要莫队之类的数据结构。