CF86D Powerful array

Powerful array(过程在注释)

题面翻译

• 给定长度为 $n$ 的序列 $a$，有 $q$ 次询问，每次询问给出两个数 $l,r$。
• 对于每次询问，设 $cn{t}_i$ 表示 $i$ 在 $a_l,a_{l+1},\cdots ,a_r$ 出现的次数，您需要求出 $\sum _{i}cn{t}_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\cdot K_s\cdot 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

样例输入 #1

3 2
1 2 1
1 2
1 3

样例输出 #1

3
6

样例 #2

样例输入 #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 $K_1=3$ , $K_2=2$ , $K_3=1$ , so the power is equal to $3^2\cdot 1+2^2\cdot 2+1^2\cdot 3=20$ .

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
struct modui{
    
    int l,r,id;
}s[N];
ll a[N],c[N],ans[N],sss=0;
int L=1,R=0,pos[N],n,t;
void add(int x){
    
    c[x]++;//因为要求Ks*Ks*s，所以每次增加一个需要在原有结果上加（Ks*Ks*x - (Ks-1)*(Ks-1)*x)
    sss+=x*(c[x]*c[x]-(c[x]-1)*(c[x]-1));
}
void del(int x){
    
    c[x]--;//,删除的话也是要相应的减去
    sss-=x*((c[x]+1)*(c[x]+1)-(c[x])*(c[x]));
}
bool cmp(modui x,modui y){
    //按左端点分块，然后在同一个块当中区间右端点要递增
	if (pos[x.l]==pos[y.l]) return x.r<y.r;//如果左在同一块当中区间右端点要递增
	return pos[x.l]<pos[y.l];
}
void query(int l,int r){
    
	while (L<l) del(a[L++]);//左指针往右移删除
	while (L>l) add(a[--L]);//左指针往左移加入
	while (R<r) add(a[++R]);//右指针往右移加入
	while (R>r) del(a[R--]);//右指针往左移删除
	return;
}
int main(){
    
    cin>>n>>t;
    int dis=sqrt(n);//块大小
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),pos[i]=i/dis;//pos标记每个数所属的分块
    for(int i=1;i<=t;i++){
    
		scanf("%d %d",&s[i].l,&s[i].r);
		s[i].id=i;
	}
    sort(s+1,s+t+1,cmp);//排序的时候按照左端点所在的块为第一关键字，右端点为第二关键字排序
    for(int i=1;i<=t;i++){
    
		query(s[i].l,s[i].r);
		ans[s[i].id]=sss;//记录答案
	}
	for(int i=1;i<=t;i++) printf("%lld\n",ans[i]);
	return 0;
}