P2709 【模板】莫队 / 小 B 的询问
题目描述
小 B 有一个长度为 n 的整数序列 a1,a2,…,an,序列中的每个元素都在 [1,k] 内。
他一共有 m 次询问。每次询问给定一个区间 [l,r],需要求出
i=1∑kci2
其中 ci 表示整数 i 在 al,al+1,…,ar 中出现的次数。
小 B 请你帮助他回答每一次询问。
输入格式
第一行输入三个整数 n,m,k(1≦n,m,k≦105) 代表序列长度、询问次数与序列的值域。
第二行输入 n 个整数 a1,a2,…,an(1≦ai≦k) 代表序列中的元素。
此后 m 行,第 i 行输入两个整数 l,r(1≦l≦r≦n) 代表第 i 次询问的区间。
输出格式
对于每次询问,新起一行输出一个整数,代表该次询问的答案。
测试样例
6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6
6
9
5
2
样例 1 解释
序列为 {1,3,2,1,1,3},k=3。四次询问的答案如下:
∙询问区间 [1,4],其中 1 出现 2 次,2 出现 1 次,3 出现 1 次,答案为 22+12+12=6;
∙询问区间 [2,6],其中 1 出现 2 次,2 出现 1 次,3 出现 2 次,答案为 22+12+22=9;
∙询问区间 [3,5],其中 1 出现 2 次,2 出现 1 次,3 出现 0 次,答案为 22+12+02=5;
∙询问区间 [5,6],其中 1 出现 1 次,2 出现 0 次,3 出现 1 次,答案为 12+02+12=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