fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define forr(i, a, b) for(int i=(a), _b=(b); i<_b; ++i)
  5. #define rep(i, b) for(int i=0, _b=(b); i<_b; ++i)
  6. #define faster ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  7. #define vi vector<int>
  8. #define ii pair<int, int>
  9. using ll = long long;
  10. using ull = unsigned long long;
  11. #define fi first
  12. #define se second
  13.  
  14. const int maxN = 3e4;
  15. int n, k, a[maxN];
  16. vi st[maxN * 4];
  17.  
  18. void build(int id, int l, int r)
  19. {
  20.     if (l == r)
  21.     {
  22.         st[id].push_back(a[l]);
  23.         return;
  24.     }
  25.     int mid = (l + r) >> 1;
  26.     build(id * 2, l, mid);
  27.     build(id * 2 + 1, mid + 1, r);
  28.     vi tmp(st[id * 2].size() + st[id * 2 + 1].size());
  29.     st[id] = tmp;
  30.     merge(st[id * 2].begin(), st[id * 2].end(), st[id * 2 + 1].begin(), st[id * 2 + 1].end(), st[id].begin());
  31. }
  32.  
  33. int get(int id, int l, int r, int u, int v, int val)
  34. {
  35.     if (l > v or r < u)
  36.         return 0;
  37.     if (l >= u and r <= v)
  38.         return st[id].size() - (upper_bound(st[id].begin(), st[id].end(), val) - st[id].begin());
  39.     int mid = (l + r) >> 1;
  40.     return get(id * 2, l, mid, u, v, val) + get(id * 2 + 1, mid + 1, r, u, v, val);
  41. }
  42.  
  43. int main()
  44. {
  45.     cin >> n;
  46.     forr(i, 1, n + 1)
  47.         cin >> a[i];
  48.     build(1, 1, n);
  49.     cin >> k;
  50.     while (k --> 0)
  51.     {
  52.         int l, r, val;
  53.         cin >> l >> r >> val;
  54.         cout << get(1, 1, n, l, r, val) << '\n';
  55.     }
  56. }
Success #stdin #stdout 0.01s 6344KB
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/tkpLSp
language:
C++ (gcc 8.3)
created:
4 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!