LG#P2709. 【模板】莫队 / 小 B 的询问

【模板】莫队 / 小 B 的询问

P2709 【模板】莫队 / 小 B 的询问

题目描述

\hspace{15pt}小 B 有一个长度为 nn 的整数序列 a1,a2,…,ana_1,a_2,\dots,a_n,序列中的每个元素都在 [1,k]\left[1,k\right] 内。

\hspace{15pt}他一共有 mm 次询问。每次询问给定一个区间 [l,r]\left[l,r\right],需要求出

∑i=1kci2\sum\limits_{i=1}^{k} c_i^2

\hspace{15pt}其中 cic_i 表示整数 ii 在 al,al+1,…,ara_l,a_{l+1},\dots,a_r 中出现的次数。

\hspace{15pt}小 B 请你帮助他回答每一次询问。

输入格式

\hspace{15pt}第一行输入三个整数 n,m,k(1≦n,m,k≦105)n,m,k\left(1 \leqq n,m,k \leqq 10^5\right) 代表序列长度、询问次数与序列的值域。

\hspace{15pt}第二行输入 nn 个整数 a1,a2,…,an(1≦ai≦k)a_1,a_2,\dots,a_n\left(1 \leqq a_i \leqq k\right) 代表序列中的元素。

\hspace{15pt}此后 mm 行,第 ii 行输入两个整数 l,r(1≦l≦r≦n)l,r\left(1 \leqq l \leqq r \leqq n\right) 代表第 ii 次询问的区间。

输出格式

\hspace{15pt}对于每次询问,新起一行输出一个整数,代表该次询问的答案。

测试样例

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

样例 1 解释

\hspace{15pt}序列为 {1,3,2,1,1,3}\{1,3,2,1,1,3\},k=3k=3。四次询问的答案如下:

∙ \hspace{23pt}\bullet\,询问区间 [1,4]\left[1,4\right],其中 11 出现 22 次,22 出现 11 次,33 出现 11 次,答案为 22+12+12=62^2+1^2+1^2=6;

∙ \hspace{23pt}\bullet\,询问区间 [2,6]\left[2,6\right],其中 11 出现 22 次,22 出现 11 次,33 出现 22 次,答案为 22+12+22=92^2+1^2+2^2=9;

∙ \hspace{23pt}\bullet\,询问区间 [3,5]\left[3,5\right],其中 11 出现 22 次,22 出现 11 次,33 出现 00 次,答案为 22+12+02=52^2+1^2+0^2=5;

∙ \hspace{23pt}\bullet\,询问区间 [5,6]\left[5,6\right],其中 11 出现 11 次,22 出现 00 次,33 出现 11 次,答案为 12+02+12=21^2+0^2+1^2=2。

7 5 4
1 2 2 3 4 2 1
1 7
2 5
3 3
4 7
6 6
15
6
1
4
1