fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. #define IOS ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  6.  
  7.  
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #include <ext/pb_ds/tree_policy.hpp>
  10. using namespace __gnu_pbds;
  11.  
  12. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>order_set;
  13. typedef pair<int, int>pr;
  14. #define all(i)     i.begin() , i.end()
  15. #define ft     first
  16. #define sn     second
  17. #define pb push_back
  18.  
  19. #define en "\n"
  20. #define dbg cout<<"rony\n"
  21.  
  22. #define MAXN 30010
  23. #define inf 1e6+5
  24. const ll mod = 1e9 + 7;
  25.  
  26. int n;
  27. int a[MAXN];
  28.  
  29. struct segment_tree
  30. {
  31.     struct NODE {
  32.         int st , EN;
  33.         vector<int>v;
  34.  
  35.         void init(int L, int R) {
  36.             st = L, EN = R;
  37.             if (L == R) v.pb(a[L]);
  38.         }
  39.     } g[3 * MAXN];
  40.  
  41.     void merge(vector<int>&A, vector<int>&B, vector<int>&C)
  42.     {
  43.         int i = 0, j = 0;
  44.         while (i < B.size() && j < C.size())
  45.         {
  46.             if (B[i] < C[j]) {
  47.                 A.pb(B[i]); i++;
  48.             }
  49.             else {
  50.                 A.pb(C[j]); j++;
  51.             }
  52.         }
  53.  
  54.         while (i < B.size()) {A.pb(B[i]); i++;}
  55.         while (j < C.size()) {A.pb(C[j]); j++;}
  56.     }
  57.  
  58.     void fill_CN(NODE &CN, NODE &LN, NODE &RN) // fill_current_node
  59.     {
  60.         merge(CN.v, LN.v, RN.v);
  61.     }
  62.  
  63.     void build(int CN, int L, int R)
  64.     {
  65.         g[CN].init(L, R);
  66.  
  67.         if (L == R ) return;
  68.         int mid = (L + R) >> 1;
  69.  
  70.         build(CN * 2, L, mid);
  71.         build(CN * 2 + 1, mid + 1, R);
  72.  
  73.         fill_CN (g[CN], g[CN * 2] , g[CN * 2 + 1]);
  74.     }
  75.  
  76.     int query(int CN, int L, int R, int val)
  77.     {
  78.         int x = g[CN].st;
  79.         int y = g[CN].EN;
  80.         if (y < L || x > R) return 0;
  81.  
  82.         if (L <= x && R >= y ) {
  83.             int ub = upper_bound(all(g[CN].v), val) - g[CN].v.begin();
  84.             return (int)g[CN].v.size() - ub;
  85.         }
  86.  
  87.         int LN = CN << 1;
  88.  
  89.         int ans = query(LN, L, R, val);
  90.         ans += query(LN | 1, L, R, val);
  91.         return ans;
  92.     }
  93.  
  94. } s_tree;
  95. void solve()
  96. {
  97.     cin >> n;
  98.     for (int i = 1; i <= n; i++) cin >> a[i];
  99.     s_tree.build(1, 1, n);
  100.  
  101.     int q; cin >> q;
  102.     while (q--)
  103.     {
  104.         int l, r, x;
  105.         cin >> l >> r >> x;
  106.         cout << s_tree.query(1, l, r, x) << en;
  107.     }
  108.  
  109. }
  110. int main()
  111. {
  112.     IOS;
  113.     ll t;
  114.     t = 1;
  115.  
  116.     // cin >> t;
  117.  
  118.     int c = 0;
  119.     while ( t-- )
  120.     {
  121.         // cout<<"Case "<<++c<<": ";
  122.         solve();
  123.     }
  124.     return 0;
  125. }
Runtime error #stdin #stdout 0.01s 6288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oCtO8f
problem KQUERY, based on SPOJ submission 31391515 (CPP14), 2023-05-22 17:57:16
language:
C++14 (gcc 8.3)
created:
1 year 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!