区间求和

对于题目中给的这个式子${\sum }_{i=l}^{r}ai\ast num(i)\backslash sum\_\{i=l\}^\{r\}ai*num(i)$，发现对于区间内的每个数字$x\mathrm{（}ai\mathrm{）}x（ai）$,出现了$num(x)num(x)$次，总的贡献为$x\ast num(x{)}^{2}x*num(x)^2$,因为本题可以离线加上数据范围在1e5之内所以直接莫队就行。 (莫队都长一个样，不会的建议自己花10分钟学一下)

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<bits/stdc++.h>
# define  PII pair<int,int>
# define  PDI pair<double,int>
# define  PIII pair<int,PII>
# define int long long
using namespace std;
const int N = 2e5+10;
const int mod = 32768;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1); 

int T,n,m,k1,k2,ans,k;
int pos[N];
int a[N];
int res[N];
int cnt[N];
struct Node{
	int id,l,r;
}q[N];
void add(int x){
	  ans-=cnt[a[x]] * cnt[a[x]] * a[x];
	  cnt[a[x]]++;
	  ans+=cnt[a[x]] * cnt[a[x]] * a[x];
	
}
void sub(int x){
	  ans-=cnt[a[x]] * cnt[a[x]] * a[x];
	  cnt[a[x]]--;
	  ans+=cnt[a[x]] * cnt[a[x]] * a[x];
}
void solve(){
	     cin >> n >> m ;
	     for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
	     int siz = sqrt(n);
	     for(int i = 1 ; i <= n ; i ++ ) pos[i] = i / siz;
	     for(int i = 1 ; i <= m ; i ++ ){
		 	  cin >> q[i].l >> q[i].r;
		 	  q[i].id = i;
		 	  
		 }
	     sort(q+1,q+1+m,[](Node x,Node y){
		 	return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];
		 });  
	     int l = 1 , r = 0;
	     for(int i = 1 ; i <= m ; i ++ ){
	     	
		 	  while(q[i].l < l ) add(--l);
		 	  while(q[i].r > r)  add(++r);
		 	  while(q[i].l > l)  sub(l++);
		 	  while(q[i].r < r)  sub(r--);
		 	  res[q[i].id] = ans;
		 	  
		 }
		 for(int i = 1 ; i <= m ; i ++ ) cout<<res[i]<<"\n";
		 
}
/*

*/
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
   // cin >> T;
     T = 1;
    while(T--){
		 solve();
	}
 	return 0;
}