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. const int maxn = 2e5 + 5;
  10. int n, q, x, y, A[maxn], B[maxn];
  11. vector<int> segtree[4 * maxn];
  12. map<int, int> seen;
  13.  
  14. void build(int r, int s, int e) {
  15. 	if(s != e) {
  16. 		int mid = (s + e) / 2;
  17. 		build(r * 2, s, mid);
  18. 		build(r * 2 + 1, mid + 1, e);
  19. 		segtree[r].resize(e - s + 1);
  20. 		merge(segtree[r * 2].begin(), segtree[r * 2].end(), segtree[r * 2 + 1].begin(), segtree[r * 2 + 1].end(), segtree[r].begin());
  21. 	} else {
  22. 		segtree[r].push_back(B[s]);
  23. 	}
  24. }
  25.  
  26. int qr(int r, int s, int e, int i, int j) {
  27. 	if(e < i || s > j) return 0;
  28. 	if(i <= s && j >= e) {
  29. 		return segtree[r].end() - upper_bound(segtree[r].begin(), segtree[r].end(), j);
  30. 	}
  31. 	int mid = (s + e) / 2;
  32. 	return qr(r * 2, s, mid, i, j) + qr(r * 2 + 1, mid + 1, e, i, j);
  33. }
  34.  
  35. int main() {
  36. 	ios::sync_with_stdio(false);
  37. 	cin.tie(0);
  38. 	cin >> n >> q;
  39. 	for(int i = 1; i <= n; i++) {
  40. 		cin >> A[i];
  41. 	}
  42. 	for(int i = n; i > 0; i--) {
  43. 		if(seen.count(A[i]) != 0) B[i] = seen[A[i]];
  44. 		else B[i] = n + 1;
  45. 		seen[A[i]] = i;
  46. 	}
  47. 	build(1, 1, n);
  48. 	for(int i = 0; i < q; i++) {
  49. 		cin >> x >> y;
  50. 		cout << qr(1, 1, n, x, y) << '\n';
  51. 	}
  52. 	return 0;
  53. }
  54.  
Success #stdin #stdout 0.01s 22496KB
comments (?)
stdin
copy 
5 3
3 2 3 1 2
1 3
2 4
1 5
stdout
copy 
2
3
3
https://ideone.com/gEssV1
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!