fork download
  1. #include <cassert>
  2. #include <cctype>
  3. #include <climits>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <sstream>
  10. #include <iomanip>
  11. #include <string>
  12. #include <vector>
  13. #include <list>
  14. #include <set>
  15. #include <map>
  16. #include <stack>
  17. #include <queue>
  18. #include <algorithm>
  19. #include <iterator>
  20. #include <utility>
  21. using namespace std;
  22.  
  23. #define pb push_back
  24. #define maxSize 30010
  25. typedef long long ll;
  26.  
  27. typedef vector<ll> vi;
  28.  
  29.  
  30.  
  31. int arr[maxSize];
  32.  
  33. vector< int > tree[maxSize * 4];
  34.  
  35. vi::iterator it;
  36.  
  37.  
  38. int bst(int i, int l, int r, int v){
  39.  
  40. int m = (l + r) / 2;
  41.  
  42. if(l==r){
  43. if( tree[i][l] > v)
  44. return 1;
  45. else
  46. return 0;
  47. }
  48.  
  49. if( tree[i][m+1] > v){
  50. return r - m + bst(i, l, m, v);
  51. }
  52. else
  53. return bst(i, m+1, r, v);
  54.  
  55.  
  56. }
  57.  
  58.  
  59. void init(int node, int b, int e){
  60.  
  61. if(b==e){
  62. // tree[node] =arr[b];
  63. tree[node].pb(arr[b]);
  64. return;
  65. }
  66.  
  67. init(node*2, b, (b+e)/2);
  68. init(node*2+1,(b+e)/2+1, e);
  69.  
  70.  
  71. for (int i = b; i <=e; ++i) {
  72.  
  73. tree[node].push_back(arr[i]);
  74. }
  75.  
  76. sort(tree[node].begin(), tree[node].end());
  77.  
  78.  
  79. }
  80.  
  81. int query(int node, int b, int e, int i, int j, int v) {
  82.  
  83.  
  84. if (j < b || e < i)
  85. return 0;
  86.  
  87. if (b >= i && e <= j) {
  88. return bst(node, 0, tree[node].size()-1, v);
  89. }
  90.  
  91. return query(node*2, b, (b+e)/2, i, j, v ) + query(node*2+1, (b+e)/2+1, e, i, j, v );
  92.  
  93. }
  94.  
  95.  
  96. int main()
  97. {
  98.  
  99. int n,q;
  100.  
  101. scanf("%d",&n);
  102.  
  103. for (int i = 1; i <=n ; ++i) {
  104.  
  105. scanf("%d",&arr[i]);
  106.  
  107. }
  108.  
  109. init(1, 1, n);
  110.  
  111. cin>>q;
  112.  
  113. for (int j = 0; j <q ; ++j) {
  114. int a,b,c;
  115. scanf("%d%d%d",&a,&b,&c);
  116. printf("%d\n",query(1, 1, n, a, b, c));
  117.  
  118. }
  119.  
  120.  
  121.  
  122. return 0;
  123. }
Runtime error #stdin #stdout 0.01s 9336KB
stdin
Standard input is empty
stdout
Standard output is empty