fork download
  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
stdin
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2 
stdout
2
0
3