fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<set>
  4. #include<iterator>
  5. #include<algorithm>
  6. using namespace std;
  7. #define fast ios::sync_with_stdio(0); cin.tie(0);
  8. const int MAX = 1e5 + 5;
  9. const int LIM = 3e5 + 5;        //equals 2 * 2^ceil(log2(n))
  10.  
  11. int input[MAX];
  12. vector<set<int> > seg(LIM);
  13. void build(int l, int r, int i)
  14. {
  15. 	if(l>r)
  16. 	return ;
  17. 	if(l == r)
  18. 	{
  19. 		set<int>s;
  20. 		s.insert(input[l]);
  21. 		seg[i] = s;
  22. 		return ;
  23. 	}
  24. 	int mid = ( l + r ) / 2;
  25. 	build(l , mid , 2*i + 1);
  26. 	build(mid+1, r, 2*i + 2);
  27. 	set_union(seg[2*i+1].begin(),seg[2*i+1].end(),seg[2*i+2].begin(),seg[2*i+2].end(),insert_iterator<set<int> >(seg[i], seg[i].begin()));
  28. }
  29.  
  30. set<int> query(int t, int i, int j, int l, int r) 
  31. {
  32. 	if (i > r || j < l){
  33. 		//base case: result of out-of-bound query
  34. 		set<int>s;
  35. 		return s;
  36. 	}
  37. 	if (l <=i && j <= r) {
  38. 		return seg[t];
  39. 	}
  40. 	int mid = (i + j) / 2;
  41. 	set<int> a = query(t*2 + 1, i, mid, l, r) ;
  42. 	set<int> b = query(t*2 + 2,  mid + 1, j, l, r);
  43. 	set<int>d;
  44. 	set_union(a.begin(),a.end(),b.begin(),b.end(),insert_iterator<set<int> >(d, d.begin()));
  45.     return d;
  46. }
  47.  
  48. int main()
  49. {
  50. 	fast
  51. 	int n;
  52. 	scanf("%d",&n);
  53. 	for(int i=0;i<n;i++)
  54. 	scanf("%d ",&input[i]);
  55.  
  56. 	build(0,n-1,0);
  57.     int q; 
  58. 	scanf("%d",&q);
  59. 	while(q--)
  60. 	{
  61. 		int l,r;
  62. 		scanf("%d %d",&l,&r);
  63. 		 printf("%d\n",query(0,0,n-1,l-1,r-1).size());
  64. 	}
  65. 	return 0;
  66. }
Success #stdin #stdout 0.01s 15768KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/jaCURU
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!