fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fi first
  6. #define se second
  7. #define mp make_pair
  8. #define pb push_back
  9. #define fbo find_by_order
  10. #define ook order_of_key
  11. #define INF 1e9
  12.  
  13. typedef long long ll;
  14. typedef pair<ll,ll> ii;
  15. typedef vector<ll> vi;
  16. typedef vector < pair<ll, ll> > vii;
  17. typedef long double ld;
  18. typedef set<int>::iterator sit;
  19. typedef map<int,int>::iterator mit;
  20. typedef vector<int>::iterator vit;
  21.  
  22. ll n, q, curL, curR, l, r, cnt[1000005], a[300005], ans, ans1[200005];
  23. vector<pair<ii, ll> > query;
  24.  
  25. bool cmp(pair<ii, ll> a, pair<ii, ll> b){
  26. 	if(a.fi.fi/int(sqrt(n)) < b.fi.fi/int(sqrt(n))){
  27. 		return 1;
  28. 	}
  29. 	else if(a.fi.fi/int(sqrt(n)) == b.fi.fi/int(sqrt(n))){
  30. 		return a.fi.se <= b.fi.se;
  31. 	}
  32. 	else{
  33. 		return 0;
  34. 	}
  35. }
  36.  
  37. int main(){
  38. 	ios_base::sync_with_stdio(false);cin.tie(NULL);
  39.     cin >> n;
  40.     for(int i = 1; i <= n; i++){
  41. 		cin >> a[i];
  42. 	}
  43. 	cin >> q;
  44. 	for(int i = 0; i < q; i++){
  45. 		cin >> l >> r;
  46. 		query.pb(mp(mp(l,r), i));
  47. 	}
  48. 	sort(query.begin(),query.end(),cmp);
  49. 	for(int i = 0; i < q; i++){
  50. 		l = query[i].fi.fi;
  51. 		r = query[i].fi.se;
  52. 		while(curR < r){
  53. 			curR++;
  54. 			cnt[a[curR]]++;
  55. 			if(cnt[a[curR]]==1){
  56. 				ans++;
  57. 			}
  58. 		}
  59. 		while(r < curR){
  60. 			cnt[a[curR]]--;
  61. 			if(cnt[a[curR]]==0){
  62. 				ans--;
  63. 			}
  64. 			curR--;
  65. 		}
  66. 		while(l < curL){
  67. 			curL--;
  68. 			cnt[a[curL]]++;
  69. 			if(cnt[a[curL]]==1){
  70. 				ans++;
  71. 			}
  72. 		}
  73. 		while(curL < l){
  74. 			cnt[a[curL]]--;
  75. 			if(cnt[a[curL]]==0){
  76. 				ans--;
  77. 			}
  78. 			curL++;
  79. 		}
  80. 		ans1[query[i].se]=ans;
  81. 	}
  82. 	for(int i = 0; i < q; i++){
  83. 		printf("%lld\n", ans1[i]);
  84. 	}
  85.  
  86. }
  87.  
Success #stdin #stdout 0s 26960KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/o9qLUW
language:
C++ (gcc 8.3)
created:
6 years 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!