fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 2e5 + 5; 
  11. const int MAX_A = 1e6 + 5; 
  12. const int B = 447; // sqrt(N)
  13. const int Q = 2e5 + 5; 
  14.  
  15. struct query {
  16. 	int l, r, idx; 
  17. 	bool operator<(const query& other) const {
  18. 		if (l / B == other.l / B) {
  19. 			return (l / B & 1) ? (r > other.r) : (r < other.r);  
  20. 		} 
  21. 		return (l < other.l); 
  22. 	}
  23. };
  24.  
  25. int n, q; 
  26. int a[N]; 
  27. vector<query> queries; 
  28.  
  29. ll cur_ans; // biến toàn cục lưu đáp án
  30. ll ans[Q]; // ans[i] = đáp án cho truy vấn thứ i 
  31. int cnt[MAX_A]; // cnt[val] = số lần xuất hiện của val
  32.  
  33. void add(int i) { // a[i]
  34. 	cur_ans -= 1ll * cnt[a[i]] * cnt[a[i]] * a[i]; 
  35. 	cnt[a[i]]++;   
  36. 	cur_ans += 1ll * cnt[a[i]] * cnt[a[i]] * a[i]; 
  37. }
  38.  
  39. void remove(int i) {
  40. 	cur_ans -= 1ll * cnt[a[i]] * cnt[a[i]] * a[i]; 
  41. 	cnt[a[i]]--; 
  42. 	cur_ans += 1ll * cnt[a[i]] * cnt[a[i]] * a[i]; 
  43. }
  44.  
  45. int main() {
  46. 	ios::sync_with_stdio(0); cin.tie(0);  	
  47. 	cin >> n >> q; 
  48. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  49.  
  50. 	for (int i = 0; i < q; i++) {
  51. 		int l, r; 
  52. 		cin >> l >> r; 
  53. 		queries.push_back({l, r, i}); 
  54. 	}
  55.  
  56. 	sort(queries.begin(), queries.end());  
  57.  
  58. 	int cur_l = 1, cur_r = 0; 
  59.  
  60. 	for (query q : queries) {
  61. 		while (cur_l > q.l) {
  62. 			cur_l--; 
  63. 			add(cur_l); 
  64. 		}
  65.  
  66. 		while (cur_l < q.l) {
  67. 			remove(cur_l); 
  68. 			cur_l++; 
  69. 		}
  70.  
  71. 		while (cur_r < q.r) {
  72. 			cur_r++; 
  73. 			add(cur_r); 
  74. 		}
  75.  
  76. 		while (cur_r > q.r) {
  77. 			remove(cur_r); 
  78. 			cur_r--; 
  79. 		}
  80.  
  81. 		ans[q.idx] = cur_ans; 
  82. 	}
  83.  
  84. 	for (int i = 0; i < q; i++) cout << ans[i] << '\n'; 
  85. }
Success #stdin #stdout 0.01s 5776KB
comments (?)
stdin
copy 
8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7
stdout
copy 
20
20
20
https://ideone.com/ZMGTyY
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!