有一个长为$a$, 值域为$[1,k]$的序列

对于每个询问区间$[l,r]$

$$
\sum^k_{i=1}{c^2_i}
$$

其中$c_i$表示数字$i$在$[l,r]$中出现的次数

莫队是由前国家队队长莫涛发明的

莫队算法的精髓就是通过合理地对询问排序,然后以较优的顺序暴力回答每个询问。处理完一个询问后,可以使用它的信息得到下一个询问区间的答案。(两个边界瞎跳)

考虑这个问题:对于上面这道题,我们知道区间$[1,5]$的答案,就可以求出$[2,6]$每个数的数量

莫队提供了这样一个排序方案:将原序列以$\sqrt{n}$为一块进行分块(分块的大小也珂以调整),排序第一关键字是询问的左端点所在块的编号,第二关键字是询问的右端点本身的位置,都是升序。然后我们用上面提到的“移动当前区间左右端点”的方法,按顺序求每个询问区间的答案,移动每一个询问区间左右端点可以求出下一个区间的答案。

1
return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];

这道题目只要分块排序亿下之后

阅读全文