区间求和

题目链接： - 题 - 目 -

一看到题目然后就想到了线段树，但是想了一会，没想到怎么维护。

然后突然一看，诶，这不是莫队的板子题嘛，然后写就A了

对于当前这种大小相等的数字的贡献为： ai * cnt *cnt ，仔细推一下即可发现。

然后就相当于莫队维护区间平方和了，但是我们再乘上 ai。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,m,a[N],cnt[N],s,res[N],cl=1,cr,bl;
struct node{
	int l,r,id;
}t[N];
int cmp(const node &s1,const node &s2){
	return (s1.l/bl==s2.l/bl)?(s1.r<s2.r):(s1.l<s2.l);
}
inline void add(int x){
	s+=a[x]*(2*cnt[a[x]]+1);	cnt[a[x]]++;
}
inline void del(int x){
	s-=a[x]*(2*cnt[a[x]]-1);	cnt[a[x]]--;
}
signed main(){
	scanf("%lld %lld",&n,&m);	bl=sqrt(n);
	for(int i=1;i<=n;i++)	scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++)	scanf("%lld %lld",&t[i].l,&t[i].r),t[i].id=i;
	sort(t+1,t+1+m,cmp);
	for(int i=1;i<=m;i++){
		int L=t[i].l;	int R=t[i].r;
		while(L<cl)	add(--cl);
		while(L>cl)	del(cl++);
		while(R<cr)	del(cr--);
		while(R>cr)	add(++cr);
		res[t[i].id]=s;
	}
	for(int i=1;i<=m;i++)	printf("%lld\n",res[i]);
	return 0;
}