Advertisement
tuki2501

KQUERY

Mar 31st, 2020
245
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.94 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct data {
  5.     int l, r, k, t, id;
  6. };
  7.  
  8. const int N = 30005;
  9. const int Q = 200005;
  10.  
  11. int n, q;
  12. int bit[N];
  13. int res[Q];
  14. data v[N + Q];
  15.  
  16. void update(int i, int v) {
  17.     for (; i <= n; i += i & -i) {
  18.         bit[i]++;
  19.     }
  20. }
  21.  
  22. int get(int i) {
  23.     int v = 0;
  24.     for (; i; i -= i & -i) {
  25.         v += bit[i];
  26.     }
  27.     return v;
  28. }
  29.  
  30. bool cmp(data a, data b) {
  31.     return a.k == b.k ? a.t > b.t : a.k > b.k;
  32. }
  33.  
  34. int main() {
  35.     ios::sync_with_stdio(0); cin.tie(0);
  36.     cin >> n;
  37.     for (int i = 1; i <= n; i++) {
  38.         cin >> v[i].k;
  39.         v[i].l = i;
  40.     }
  41.     cin >> q;
  42.     for (int i = 1; i <= q; i++) {
  43.         cin >> v[n + i].l >> v[n + i].r >> v[n + i].k;
  44.         v[n + i].t = 1;
  45.         v[n + i].id = i;
  46.     }
  47.     sort(v + 1, v + n + q + 1, cmp);
  48.     for (int i = 1; i <= n + q; i++) {
  49.         if (v[i].t == 0) update(v[i].l, 1);
  50.         else res[v[i].id] = get(v[i].r) - get(v[i].l - 1);
  51.     }
  52.     for (int i = 1; i <= q; i++) {
  53.         cout << res[i] << '\n';
  54.     }
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement