Powerful array
题意翻译
- 给定长度为 $n$ 的序列 $a$,有 $q$ 次询问,每次询问给出两个数 $l,r$。
- 对于每次询问,设 $cnt_i$ 表示 $i$ 在 $a_l,a_{l+1},\cdots,a_r$ 出现的次数,您需要求出 $\displaystyle\sum_i cnt_i^2\cdot i$。
- $1\le n,q\le 2\times 10^5$,$1\le a_i\le 10^6$,$1\le l\le r\le n$。
题目描述
An array of positive integers $ a_{1},a_{2},...,a_{n} $ is given. Let us consider its arbitrary subarray $ a_{l},a_{l+1}...,a_{r} $ , where $ 1<=l<=r<=n $ . For every positive integer $ s $ denote by $ K_{s} $ the number of occurrences of $ s $ into the subarray. We call the power of the subarray the sum of products $ K_{s}·K_{s}·s $ for every positive integer $ s $ . The sum contains only finite number of nonzero summands as the number of different values in the array is indeed finite.
You should calculate the power of $ t $ given subarrays.
输入输出格式
输入格式
First line contains two integers $ n $ and $ t $ ( $ 1<=n,t<=200000 $ ) — the array length and the number of queries correspondingly.
Second line contains $ n $ positive integers $ a_{i} $ ( $ 1<=a_{i}<=10^{6} $ ) — the elements of the array.
Next $ t $ lines contain two positive integers $ l $ , $ r $ ( $ 1<=l<=r<=n $ ) each — the indices of the left and the right ends of the corresponding subarray.
输出格式
Output $ t $ lines, the $ i $ -th line of the output should contain single positive integer — the power of the $ i $ -th query subarray.
Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preferred to use cout stream (also you may use %I64d).
输入输出样例
输入样例 #1
3 2
1 2 1
1 2
1 3
输出样例 #1
3
6
输入样例 #2
8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7
输出样例 #2
20
20
20
说明
Consider the following array (see the second sample) and its \[2, 7\] subarray (elements of the subarray are colored):
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF86D/5e3c36b108711f9f95c3c3519472e9f583328f8b.png) Then $ K_{1}=3 $ , $ K_{2}=2 $ , $ K_{3}=1 $ , so the power is equal to $ 3^{2}·1+2^{2}·2+1^{2}·3=20 $ .