fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define len(s) (int)s.size()
  4.  
  5. using namespace std;
  6. using ll = int64_t;
  7. using ld = long double;
  8. using pll = pair<ll, ll>;
  9. using pii = pair<int, int>;
  10.  
  11. const ll INF = 1e18;
  12.  
  13. const int MAXN = 2e5 + 11;
  14. int n, q, a[MAXN], b[MAXN];
  15. vector<int> st[MAXN * 2];
  16.  
  17. void build()
  18. {
  19.     for (int i = 0; i < n; ++i)
  20.     {
  21.         st[n + i].push_back(a[i]);
  22.     }
  23.  
  24.     for (int i = n - 1; i >= 1; --i)
  25.     {
  26.         merge(st[i * 2].begin(), st[i * 2].end(),
  27.               st[i * 2 + 1].begin(), st[i * 2 + 1].end(),
  28.               back_inserter(st[i]));
  29.     }
  30. }
  31.  
  32. int query(int l, int r, int k)
  33. {
  34.     l += n, r += n;
  35.  
  36.     int res = 0;
  37.  
  38.     while (l < r)
  39.     {
  40.         if (l & 1)
  41.         {
  42.             res += st[l].size() - (upper_bound(st[l].begin(), st[l].end(), k) - st[l].begin());
  43.             ++l;
  44.         }
  45.  
  46.         if (r & 1)
  47.         {
  48.             --r;
  49.             res += st[r].size() - (upper_bound(st[r].begin(), st[r].end(), k) - st[r].begin());
  50.         }
  51.  
  52.         l >>= 1;
  53.         r >>= 1;
  54.     }
  55.  
  56.     return res;
  57. }
  58.  
  59. int main()
  60. {
  61.     ios_base::sync_with_stdio(false);
  62.     cin.tie(NULL);
  63.     cout.tie(NULL);
  64.     // freopen("input.txt", "r", stdin);
  65.     // freopen("output.txt", "w", stdout);
  66.     cin >> n;
  67.  
  68.     for (int i = 0; i < n; ++i)
  69.     {
  70.         cin >> a[i];
  71.     }
  72.  
  73.     build();
  74. 	cin >> q;
  75.     while (q--)
  76.     {
  77.         int l, r, k;
  78.         cin >> l >> r >> k;
  79.         cout << query(l - 1, r, k) << "\n";
  80.     }
  81. }
Success #stdin #stdout 0.01s 12972KB
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/8UINJo
language:
C++14 (gcc 8.3)
created:
17 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!