apl-mhd

kquery spoj

Dec 1st, 2019
202
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. int arr[maxSize];
  30. vector< int > tree[maxSize * 4];
  31. vi::iterator it;
  32.  
  33. int bst(int i, int l, int r, int v){
  34.  
  35.     int m = (l + r) / 2;
  36.  
  37.     if(l==r){
  38.         if( tree[i][l] > v)
  39.             return 1;
  40.         else
  41.             return 0;
  42.     }
  43.  
  44.     if( tree[i][m+1] > v){
  45.         return  r - m + bst(i, l, m, v);
  46.     }
  47.     else
  48.         return bst(i, m+1, r, v);
  49.  
  50. }
  51.  
  52.  
  53. void init(int node, int b, int e){
  54.  
  55.         if(b==e){
  56.            // tree[node] =arr[b];
  57.            tree[node].pb(arr[b]);
  58.             return;
  59.         }
  60.  
  61.         init(node*2, b, (b+e)/2);
  62.         init(node*2+1,(b+e)/2+1, e);
  63.  
  64.     merge(tree[node*2].begin(), tree[node*2].end(),tree[node*2+1].begin(), tree[node*2+1].end(), back_inserter(tree[node]));
  65.  
  66. }
  67.  
  68.  
  69.  
  70.  
  71. int query(int node, int b, int e, int i, int j, int v) {
  72.  
  73.     if (j < b || e < i)
  74.         return 0;
  75.  
  76.     if (b >= i && e <= j) {
  77.         return bst(node, 0, tree[node].size()-1, v);
  78.     }
  79.  
  80.     return query(node*2, b, (b+e)/2, i, j, v )  + query(node*2+1, (b+e)/2+1, e, i, j, v );
  81. }
  82.  
  83.  
  84. int main()
  85. {
  86.  
  87.     int n,q;
  88.     scanf("%d",&n);
  89.  
  90.     for (int i = 1; i <=n ; ++i) {
  91.         scanf("%d",&arr[i]);
  92.     }
  93.  
  94.     init(1, 1, n);
  95.     scanf("%d", &q);
  96.  
  97.     for (int j = 0; j <q ; ++j) {
  98.         int a,b,c;
  99.         scanf("%d%d%d",&a,&b,&c);
  100.         printf("%d\n",query(1, 1, n, a, b, c));
  101.  
  102.     }
  103.  
  104.     return 0;
  105. }
RAW Paste Data