fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MX = 2e5 + 7;
  5. const int MXN = 240000;
  6. typedef pair<int,int> pii;
  7. typedef pair<pii, int> piii;
  8. #define f first
  9. #define s second
  10. int SZ, n, q, Arr[MX], Ans[MX], K[MX], tree[MXN];
  11. piii queries[MX];
  12.  
  13. bool cmp(const piii &x, const piii &y){
  14. 	int _x = x.f.f/SZ;
  15. 	int _y = y.f.f/SZ;
  16.  
  17. 	if(_x != _y) return _x < _y;
  18. 	return x.f.s < y.f.s;
  19. }
  20.  
  21. void update(int x, int val){
  22. 	for(; x < MXN ; tree[x] += val, x += x & -x) ;
  23. }
  24.  
  25. int query(int x){
  26. 	int sum = 0;
  27. 	for(; x > 0 ; sum += tree[x], x -= x & -x) ;
  28. 	return sum;
  29. }
  30.  
  31. void add(int x){
  32. 	update(x, 1);
  33. }
  34.  
  35. void remove(int x){
  36. 	update(x, -1);
  37. }
  38.  
  39. int main() {
  40. 	scanf("%d", &n);
  41. 	SZ = static_cast<int> (sqrt(n));
  42.  
  43. 	vector<int> V;
  44.  
  45. 	for(int i = 0; i < n; i++){
  46. 		scanf("%d", &Arr[i]);
  47. 		V.push_back(Arr[i]);
  48. 	}
  49.  
  50. 	scanf("%d", &q);
  51.  
  52. 	for(int i = 0; i<q; i++){
  53. 		scanf("%d %d %d", &queries[i].f.f, &queries[i].f.s, &K[i]);
  54. 		queries[i].f.f--;
  55. 		queries[i].f.s--;
  56. 		queries[i].s = i;
  57. 		V.push_back(K[i]);
  58. 	}
  59.  
  60. 	sort(queries, queries + q, cmp);
  61. 	sort(V.begin(), V.end());
  62. 	//V.resize(unique(V.begin(), V.end()) - V.begin());
  63.  
  64. 	for(int i = 0; i<n; i++){
  65. 		int val = upper_bound(V.begin(), V.end(), Arr[i]) - V.begin();
  66. 		Arr[i] = val;
  67. 	}
  68.  
  69. 	for(int i = 0; i<q; i++){
  70. 		int val = upper_bound(V.begin(), V.end(), K[i]) - V.begin();
  71. 		K[i] = val;
  72. 	}
  73.  
  74. 	int left = 0, right = -1, val = V.size();
  75. 	for(int i = 0; i<q; i++){
  76. 		int l = queries[i].f.f;
  77. 		int r = queries[i].f.s;
  78. 		int id = queries[i].s;
  79.  
  80. 	    while(right < r){
  81. 			right++;
  82. 			add(Arr[right]);
  83. 		}
  84.  
  85. 		while(right > r){
  86. 		    remove(Arr[right]);
  87. 			right--;
  88. 		}
  89.  
  90. 		while(left < l){
  91. 			remove(Arr[left]);
  92. 			left++;
  93. 		}
  94.  
  95. 		while(left > l){
  96. 			left--;
  97. 			add(Arr[left]);
  98. 		}
  99.  
  100. 		Ans[id] = query(val) - query(K[id]); 
  101. 	}
  102.  
  103. 	for(int i = 0; i<q; i++) printf("%d\n", Ans[i]);
  104. 	return 0;
  105. }
Success #stdin #stdout 0s 9104KB
comments (?)
stdin
copy 
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2
stdout
copy 
2
0
3
https://ideone.com/4COpOu
language:
C++14 (gcc 8.3)
created:
7 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!