5303 - 第二十四章 双指针和莫队:区间数字统计
时间限制 : 1 秒
内存限制 : 128 MB
有一个长为 n 的整数序列 a,值域为 [1,k]。
他一共有 m 个询问,每个询问给定一个区间 [l,r],求:
\sum\limits_{i=1}^k c_i^2
其中 c_i 表示数字 i 在 [l,r] 中的出现次数。
输入
第一行三个整数 n,m,k。
第二行 n 个整数,表示序列。
接下来的 m 行,每行两个整数 l,r。
输出
输出 m 行,每行一个整数,对应一个询问的答案。
样例
输入
6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6
输出
6 9 5 2
提示
【数据范围】
对于 100\% 的数据,1\le n,m,k \le 5\times 10^4。