小B的询问(Little Bs Queries)

小 B 有一个长为 $n$ 的整数序列 $a$ ，值域为 $[1,k]$ 。
他一共有 $m$ 个询问，每个询问给定一个区间 $[l,r]$ ，求：
$\sum\limits_{i=1}^k c_i^2$

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

小 B 请你帮助他回答询问。

第一行三个整数 $n,m,k$ 。

第二行 $n$ 个整数，表示小 B 的序列。

接下来的 $m$ 行，每行两个整数 $l,r$ 。

输出 $m$ 行，每行一个整数，对应一个询问的答案。

6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6

【数据范围】
对于 $100\%$ 的数据， $1\le n,m,k \le 10^5$ 。

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1800。

Subtask	分值	测试点编号	说明
0	10	1	样例
1	20	2~7	小规模 n,m,k≤2000 / 边界 n=m=k=1 / 单点区间 l=r 恒输出1
2	15	8~11	Hack: 全序列单一数值答案达 n^2=10^10 卡32位溢出 / Hack: 全序列互不相同恒输出区间长度
3	30	12~20	满规模 n=m=k=10^5 莫队平方和离线查询压力
4	25	21~25	随机值域与区间跨度回归测试

出处：原题链接

#P2709. 小B的询问(Little Bs Queries)