fork download
copy 
  1. #include<iostream>
  2. #include<cmath>
  3. #include<vector>
  4. #include<climits>
  5. #include<algorithm>
  6. #include<numeric>
  7. #include<iomanip>
  8. #include<map>
  9. #include<unordered_map>
  10. #include<set>
  11. #include<random>
  12. #include<cassert>
  13. using namespace std;
  14. #define ll long long int
  15. #define ld long double
  16.  
  17. // MO's Algorithms
  18.  
  19.  
  20. struct node{
  21. 	// for query
  22. 	ll l; // begin
  23. 	ll r; // end
  24. 	ll in ; // index
  25. 	};
  26. ll cnt=0;
  27.  
  28. bool cmp(node A, node B)
  29. {
  30. if(A.l == B.l)
  31. {
  32. 	return (A.r<B.r);
  33. }
  34. return (A.l<B.l);	
  35. }
  36.  
  37. vector<ll> f(1000005,0);
  38. ll beg=1, End=0;
  39.  
  40.  
  41. int main()
  42. {
  43. ios_base::sync_with_stdio(false);
  44. cin.tie(NULL);	
  45.  
  46. ll n;
  47. cin>>n;
  48. ll a[n+2];
  49.  
  50. for(ll i=1;i<=n;i++){cin>>a[i];}
  51. ll q;
  52. cin>>q;
  53. node Q[q+1];
  54. ll ans[n+3] ;
  55. for(ll i=1;i<=q;i++)
  56. {
  57. 	ll s ,e;
  58. 	cin>>s>>e;
  59. 	Q[i].l = s;
  60. 	Q[i].r=e;
  61. 	Q[i].in=i;
  62. }
  63. // sort:
  64.  
  65. sort(Q+1,Q+1+q,cmp);
  66. for(ll i=1;i<=q;i++)
  67. {
  68. 	ll st = Q[i].l;
  69. 	ll en = Q[i].r;
  70.  
  71. 	// change freq as per req;
  72. 	while(beg<st)
  73. 	{
  74. 	// rem cur 
  75. 	 f[a[beg]]--;
  76. 	 if(f[a[beg]]==0){cnt--;}
  77. 	 beg++;
  78. 	}
  79. 	while(beg>st)
  80. 	{
  81. 	beg--;	
  82. 	f[a[beg]]++;
  83. 	if(f[a[beg]]==1){cnt++;}	
  84. 	}
  85.  
  86. 	while(End<en)
  87. 	{
  88. 	End++;
  89. 	f[a[End]]++;
  90. 	if(f[a[End]]==1){cnt++;}	
  91. 	}
  92.  
  93. 	while(End>en)
  94. 	{
  95. 	f[a[End]]--;
  96. 	if(f[a[End]]==0){cnt--;}
  97. 	End--;	
  98. 	}
  99.  
  100. 	ans[Q[i].in] = cnt ;
  101. }
  102.  
  103. for(ll i=1;i<=q;i++)
  104. {
  105. cout<<ans[i]<<endl;	
  106. }
  107.  
  108. return 0;
  109. }
  110.  
Success #stdin #stdout 0s 11008KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/XQriQm
D query
language:
C++14 (gcc 8.3)
created:
5 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!