CF86D Powerful array

题意翻译

题意：给出一个n个数组成的数列a，有t次询问，每次询问为一个[l,r]的区间，求区间内每种数字出现次数的平方×数字的值的和。

输入：第一行2个正整数n,t。

接下来一行n个正整数，表示数列

接下来t行，每行两个正整数l,r，为一次询问。

输出：t行，分别为每次询问的答案。

数据范围：

题目描述

An array of positive integers $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

输入输出格式

输入格式：

First line contains two integers

Second line contains $a_{i} ai ( 1<=ai<=106 1<=a_{i}<=10^{6} 1<=ai<=106 ) — the elements of the array.$

输出格式：

Output

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：

输出样例#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):

Then

Solution：

　　本题莫队水题。

　　维护一下区间内每个数的出现次数，每次左右移动指针的同时，更新下数的次数以及平方和就好了。

代码：

/*Code by 520 -- 10.19*/
#include<bits/stdc++.h>
#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
",ans[i]);
    return 0;
}