题意：给出一个n个数组成的数列a，有t次询问，每次询问为一个[l,r]的区间，求区间内每种数字出现次数的平方×数字的值 的和。
输入：第一行2个正整数n,t。
接下来一行n个正整数，表示数列a1~an的值。
接下来t行，每行两个正整数l,r，为一次询问。
输出：t行，分别为每次询问的答案。
数据范围：1≤n,t≤2∗105,1≤ai≤106,1≤l,r≤n
题目描述An array of positive integers a1,a2,...,an a_{1},a_{2},...,a_{n} a1,a2,...,an is given. Let us consider its arbitrary subarray al,al+1...,ar a_{l},a_{l+1}...,a_{r} al,al+1...,ar , where 1<=l<=r<=n 1<=l<=r<=n 1<=l<=r<=n . For every positive integer s s s denote by Ks K_{s} Ks the number of occurrences of s s s into the subarray. We call the power of the subarray the sum of products Ks⋅Ks⋅s K_{s}·K_{s}·s Ks⋅Ks⋅s for every positive integer s s 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 t t given subarrays.
输入输出格式输入格式：
First line contains two integers n n n and t t t ( 1<=n,t<=200000 1<=n,t<=200000 1<=n,t<=200000 ) — the array length and the number of queries correspon����,����dingly.
Second line contains n n n positive integers ai a_{i} ai ( 1<=ai<=106 1<=a_{i}<=10^{6} 1<=ai<=106 ) — the elements of the array.
Next t t t lines contain two positive integers l l l , r r r ( 1<=l<=r<=n 1<=l<=r<=n 1<=l<=r<=n ) each — the indices of the left and the right ends of the corresponding subarray.
输出格式：
Output t t t lines, the i i i -th line of the output should contain single positive integer — the power of the i i 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 21 2 11 21 3
输出样例#1：
36
输入样例#2：
8 31 1 2 2 1 3 1 12 71 62 7
输出样例#2：
202020说明
Consider the following array (see the second sample) and its [2, 7] subarray (elements of the subarray are colored):
Then K1=3 , K2=2 , K3=1, so the power is equal to 32⋅1+22⋅2+12⋅3=20.
Solution：
本题莫队水题。
维护一下区间内每个数的出现次数，每次左右移动指针的同时，更新下数的次数以及平方和就好了。
代码：
/*Code by 520 -- 10.19*/#include#define il inline#define ll long long#define RE register#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)#define calc(x) (1ll*x*x)using namespace std;const int N=1000005;int n,m,a[N],c[N],bl[N];ll ans[N],tot;struct node{ int l,r,id; bool operator < (const node &a) const {return bl[l]==bl[a.l]?r<a.r:l<a.l;}}t[N];int gi(){ int a=0;char x=getchar(); while(x<'0'||x>'9') x=getchar(); while(x>='0'&&x<='9') a=(a<<3)+(a<<1)+(x^48),x=getchar(); return a;}il void add(int x){tot-=calc(c[a[x]])*a[x],c[a[x]]++,tot+=calc(c[a[x]])*a[x];}il void del(int x){tot-=calc(c[a[x]])*a[x],c[a[x]]--,tot+=calc(c[a[x]])*a[x];}int main(){ n=gi(),m=gi(); int blo=sqrt(n); For(i,1,n) a[i]=gi(),bl[i]=(i-1)/blo+1; For(i,1,m) t[i]=node{gi(),gi(),i}; sort(t+1,t+m+1); for(RE int i=1,l=1,r=0;i<=m;i++){ while(l<t[i].l) del(l),l++; while(l>t[i].l) --l,add(l); while(r<t[i].r) ++r,add(r); while(r>t[i].r) del(r),r--; ans[t[i].id]=tot; } For(i,1,m) printf("%lld\n",ans[i]); return 0;}