CF86D Powerful array

题意翻译

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

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

接下来一行n个正整数，表示数列a1~an的值。

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

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

数据范围：1≤n,t≤2∗10⁵,1≤ai≤10⁶,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 correspondingly.

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：

输出样例#1：

3

6

输入样例#2：

8 3

1 1 2 2 1 3 1 1

2 7

1 6

2 7

输出样例#2：

说明

Consider the following array (see the second sample) and its [2, 7] subarray (elements of the subarray are colored):

CF86D Powerful array 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<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=;

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=;char x=getchar();

    while(x<''||x>'') x=getchar();

    while(x>=''&&x<='') a=(a<<)+(a<<)+(x^),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,,n) a[i]=gi(),bl[i]=(i-)/blo+;

    For(i,,m) t[i]=node{gi(),gi(),i};

    sort(t+,t+m+);

    for(RE int i=,l=,r=;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,,m) printf("%lld\n",ans[i]);

    return ;

}

秒客网

CF86D Powerful array

题意翻译

题目描述

输入输出格式

输入输出样例

说明

相关文章