fork(1) download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Query {
  6. int l, r, val;
  7. int ans;
  8. };
  9.  
  10. const int maxn = 30010;
  11. const int maxq = 200010;
  12. int n, q;
  13. pair<int, int> a[maxn];
  14. Query qr[maxq];
  15.  
  16. vector<int> val_it[maxn * 2];
  17. vector<Query*> qr_it[maxn * 2];
  18.  
  19. int main() {
  20. #ifdef LOCAL
  21. freopen("main.inp", "r", stdin);
  22. freopen("main.out", "w", stdout);
  23. #endif
  24. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  25. cin >> n;
  26. for (int i = 0; i < n; ++i) {
  27. cin >> a[i].first;
  28. a[i].second = i;
  29. }
  30.  
  31. cin >> q;
  32. vector<Query*> temp_qr;
  33. for (int i = 0; i < q; ++i) {
  34. cin >> qr[i].l >> qr[i].r >> qr[i].val;
  35. --qr[i].l;
  36. qr[i].ans = 0;
  37. temp_qr.push_back(qr + i);
  38. }
  39.  
  40. sort(a, a + n, greater<>());
  41. sort(temp_qr.begin(), temp_qr.end(), [](const Query* u, const Query* v) { return u->val > v->val; });
  42.  
  43. for (int i = 0; i < n; ++i) {
  44. for (int p = a[i].second + n; p > 0; p >>= 1)
  45. val_it[p].push_back(a[i].first);
  46. }
  47.  
  48. for (auto cur_qr: temp_qr) {
  49. for (int l = cur_qr->l + n, r = cur_qr->r + n; l < r; l >>= 1, r >>= 1) {
  50. if (l & 1) qr_it[l++].push_back(cur_qr);
  51. if (r & 1) qr_it[--r].push_back(cur_qr);
  52. }
  53. }
  54.  
  55. for (int root = 1; root < 2 * n; ++root) {
  56. auto& vi = val_it[root];
  57. auto& qi = qr_it[root];
  58. if (vi.empty() or qi.empty()) continue;
  59. int ptr_v = 0;
  60. for (auto cur_qr: qi) {
  61. while (ptr_v < (int)vi.size() and vi[ptr_v] > cur_qr->val) ++ ptr_v;
  62. cur_qr->ans += ptr_v;
  63. }
  64. }
  65.  
  66. for (int i = 0; i < q; ++i) cout << qr[i].ans << '\n';
  67.  
  68. return 0;
  69. }
  70.  
Success #stdin #stdout 0s 6504KB
stdin
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2 
stdout
2
0
3