fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 3e4 + 11;
  6. int n, a[MAXN], l, r, k, q;
  7. vector<vector<int>> st(MAXN * 4);
  8.  
  9. void build(int id, int l, int r) {
  10.     if (l == r) {
  11.         st[id].push_back(a[l]);
  12.         return ;
  13.     }
  14.     int mid = (l + r) / 2;
  15.     build(id*2, l, mid);
  16.     build(id*2+1, mid+1, r);
  17.  
  18. 	st[id].resize(st[id * 2].size() + st[id * 2 + 1].size());
  19.     merge(st[id*2].begin(), st[id*2].end(), st[id*2+1].begin(), st[id*2+1].end(), st[id].begin());
  20. }
  21.  
  22. int get(int id, int l, int r, int u, int v, int k)
  23. {
  24.     if (v < l || r < u)
  25.         return 0;
  26.  
  27.     if (u <= l && r <= v)
  28.     {
  29.         return st[id].size() - (upper_bound(st[id].begin(), st[id].end(), k) - st[id].begin());
  30.     }
  31.  
  32.     int mid = (l + r) / 2;
  33.     return get(id * 2, l, mid, u, v, k) + get(id * 2 + 1, mid + 1, r, u, v, k);
  34. }
  35.  
  36. int main()
  37. {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(NULL);
  40.     cin >> n;
  41.  
  42.     for (int i = 1; i <= n; ++i)
  43.         cin >> a[i];
  44.  
  45.     build(1, 1, n);
  46.     cin >> q;
  47.     while (q--)
  48.     {
  49.         cin >> l >> r >> k;
  50.         cout << get(1, 1, n, l, r, k) << "\n";
  51.     }
  52.  
  53.     return 0;
  54. }
  55.  
Success #stdin #stdout 0.01s 5908KB
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/sLHFUI
language:
C++ (gcc 8.3)
created:
12 days 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!