fork download
copy 
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <algorithm>
  4. using namespace std;
  5. typedef long long ll;
  6. #define MG 500
  7. #define MN 100005
  8. #define MM 1000005
  9. int zz;
  10. inline int get_id(int x, int y) { return (x/zz)*zz + (y/zz); }
  11. struct Query {
  12. 	int lo, hi, id, ord;
  13. 	long long res;
  14. } q[MN];
  15. inline bool cmp(Query q1, Query q2) { return q1.id < q2.id; }
  16. inline bool fin(Query q1, Query q2) { return q1.ord < q2.ord; }
  17. int n, Q, a[MN], d[MM];
  18. int main() {
  19. 	int i, j, k;
  20. 	scanf("%d%d",&n,&Q);
  21. 	zz = (int)sqrt(n+0.0);
  22. 	for (i = 0; i < n; i++) scanf("%d",&a[i]);
  23. 	for (k = 1; k <= Q; k++) {
  24. 		scanf("%d%d",&q[k].lo,&q[k].hi); q[k].lo--, q[k].hi--;
  25. 		q[k].id = get_id(q[k].lo, q[k].hi);
  26. 		q[k].ord = k;
  27. 	}
  28. 	sort(q+1, q+Q+1, cmp);
  29. 	for (k = 1; k <= Q; k++) {
  30. 		if (k == 1) {
  31. 			for (i = q[k].lo; i <= q[k].hi; i++) q[k].res += (ll)(2*(d[a[i]]++)+1)*(ll)(a[i]);
  32. 		} else {
  33. 			q[k].res = q[k-1].res;
  34. 			if (q[k-1].hi < q[k].hi) for (i = q[k-1].hi+1; i <= q[k].hi; i++) q[k].res += (ll)(2*(d[a[i]]++)+1)*(ll)(a[i]);
  35. 			if (q[k].lo < q[k-1].lo) for (i = q[k].lo; i < q[k-1].lo; i++) q[k].res += (ll)(2*(d[a[i]]++)+1)*(ll)(a[i]);
  36. 			if (q[k].lo > q[k-1].lo) for (i = q[k-1].lo; i < q[k].lo; i++) q[k].res -= (ll)(2*(d[a[i]]--)-1)*(ll)(a[i]);
  37. 			if (q[k-1].hi > q[k].hi) for (i = q[k].hi+1; i <= q[k-1].hi; i++) q[k].res -= (ll)(2*(d[a[i]]--)-1)*(ll)(a[i]);
  38. 		}
  39. 	}
  40. 	sort(q+1, q+Q+1, fin);
  41. 	for (k = 1; k <= Q; k++) printf("%lld\n",q[k].res);
  42. 	return 0;
  43. }
Success #stdin #stdout 0s 9984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YDryM4
language:
C++ (gcc 8.3)
created:
10 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!