fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include<map>
  6.  
  7. using namespace std;
  8.  
  9. struct Query {
  10. 	int L, R, i;
  11. 	Query() {}
  12. 	Query(int left, int right, int idx): L(left), R(right), i(idx) {}
  13. };
  14.  
  15. const int maxn = 2e5 + 5;
  16. int n, q, x, y, A[maxn], B[maxn], fenwick[maxn];
  17. vector<Query> queries;
  18. vector<int> ans;
  19. map<int, int> seen;
  20.  
  21. bool cmp(Query &q1, Query &q2) {
  22. 	return q1.L < q2.L;
  23. }
  24.  
  25. void upd(int i, int v) { // fenwick tree is 1-indexed
  26. 	if(i == 0) return;
  27. 	int c = i;
  28. 	while(c <= n) {
  29. 		fenwick[c] += v;
  30. 		c += (c & -c);
  31. 	}
  32. }
  33.  
  34. int qr(int i) { // fenwick tree is 1-indexed
  35. 	if(i == 0) return 0;
  36. 	int c = i, ans = 0;
  37. 	while(c > 0) {
  38. 		ans += fenwick[c];
  39. 		c -= (c & -c);
  40. 	}
  41. 	return ans;
  42. }
  43.  
  44. void printFenwick() {
  45. 	for(int i = 1; i <= n; i++) {
  46. 		cout << qr(i) - qr(i - 1) << " ";
  47. 	}
  48. 	cout << '\n';
  49. }
  50.  
  51. int main() {
  52. 	ios::sync_with_stdio(false);
  53. 	cin.tie(0);
  54. 	cin >> n >> q;
  55. 	for(int i = 1; i <= n; i++) {
  56. 		cin >> A[i];
  57. 	}
  58. 	for(int i = n; i > 0; i--) {
  59. 		if(seen.count(A[i]) != 0) B[i] = seen[A[i]];
  60. 		seen[A[i]] = i;
  61. 	}
  62. 	seen.clear();
  63. 	for(int i = 1; i <= n; i++) {
  64. 		if(seen.count(A[i]) == 0) upd(i, 1);
  65. 		seen[A[i]] = 1;
  66. 	}
  67. 	queries.resize(q), ans.resize(q);
  68. 	for(int i = 0; i < q; i++) {
  69. 		cin >> x >> y;
  70. 		queries[i] = {x, y, i};
  71. 	}
  72. 	sort(queries.begin(), queries.end(), cmp);
  73. 	for(int i = 0, beforeL = 1; i < q; i++) {
  74. 		int curL = queries[i].L, curR = queries[i].R;
  75. 		while(beforeL < curL) {
  76. 			upd(B[beforeL], 1);
  77. 			beforeL++;
  78. 		}
  79. 		ans[queries[i].i] = qr(curR) - qr(curL - 1);
  80. 	}
  81. 	for(auto &qr_ans : ans) cout << qr_ans << '\n';
  82. 	return 0;
  83. }
  84.  
Success #stdin #stdout 0s 4552KB
comments (?)
stdin
copy 
5 3
3 2 3 1 2
1 3
2 4
1 5
stdout
copy 
2
3
3
https://ideone.com/lUHOcz
language:
C++14 (gcc 8.3)
created:
4 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!