题解：P11659 小夫
__cstdio__cpp
·
·
题解
考虑每一个 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}}) ,
展开可得:
对于区间范围内左侧没有 $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)$。
这样就做完了，并不需要莫队之类的数据结构。