fork download 
  1. #include<bits/stdc++.h>
  2. #define MAXN 200010
  3. #define MAXX 1000010
  4. using namespace std;
  5. int block;
  6. long long arr[MAXN+1],freq[MAXX+1],sol[MAXN+1];
  7. struct query{
  8. 	int l,r,i;
  9. }qry[MAXN+1];
  10. bool comp(query q1,query q2){
  11. 	if(q1.l!=q2.l)
  12. 		return (q1.l/block)<(q2.l/block);
  13. 	return q1.r<q2.r;
  14. }
  15. int main(){
  16. 	ios::sync_with_stdio(false);
  17. 	int n,t,l,r,lx,rx;
  18. 	long long x=0;
  19. 	cin>>n>>t;
  20. 	block=sqrt(n);
  21. 	for(int i=0;i<n;i++)
  22. 		cin>>arr[i];
  23. 	for(int i=0;i<t;i++){
  24. 		cin>>qry[i].l>>qry[i].r;
  25. 		qry[i].l--;
  26. 		qry[i].r--;
  27. 		qry[i].i=i;
  28. 	}
  29. 	sort(qry,qry+t,comp);
  30. 	l=0;
  31. 	r=-1;
  32. 	for(int i=0;i<t;i++){
  33. 		lx=qry[i].l;
  34. 		rx=qry[i].r;
  35. 		while(l>lx){
  36. 			l--;
  37. 			x+=(((2LL*freq[arr[l]])+1)*arr[l]);
  38. 			freq[arr[l]]++;
  39. 		}
  40. 		while(l<lx){
  41. 			x-=(((2LL*freq[arr[l]])-1)*arr[l]);
  42. 			freq[arr[l]]--;
  43. 			l++;
  44. 		}
  45. 		while(r<=rx){
  46. 			x+=(((2LL*freq[arr[r]])+1)*arr[r]);
  47. 			freq[arr[r]]++;
  48. 			r++;
  49. 		}
  50. 		while(r>(rx+1)){
  51. 			r--;
  52. 			x-=(((2LL*freq[arr[r]])-1)*arr[r]);
  53. 			freq[arr[r]]--;
  54. 		}
  55. 		sol[qry[i].i]=x;
  56. 	}
  57. 	for(int i=0;i<t;i++)
  58. 		cout<<sol[i]<<"\n";
  59. 	return 0;
  60. }
Success #stdin #stdout 0s 28520KB
comments (?)
stdin 
3 2
1 2 1
1 2
1 3
stdout 
3
6
https://ideone.com/kKKV97
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!