newb_ie

Wavlet Tree

Aug 3rd, 2021
616
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxN = 100;
  5. int a[maxN];
  6.  
  7. struct WavletTree {
  8.     int low,high;
  9.     WavletTree *l, *r;
  10.     vector<int> b;
  11.     WavletTree (int *from,int *to,int x,int y) {
  12.         low = x,high = y;
  13.         if (low==high or from >= to) return;
  14.         int mid = low + (high - low) / 2;
  15.         b.reserve(to - from + 1);
  16.         b.push_back(0);
  17.         auto f = [mid] (int x) {return x <= mid;};
  18.         for (auto it = from; it != to; ++it) b.push_back(b.back() + f(*it));
  19.         auto pivot = stable_partition(from,to,f);
  20.         l = new WavletTree(from,pivot,low,mid);
  21.         r = new WavletTree(pivot,to,mid + 1,high);
  22.     }
  23.     int kth (int l,int r,int k) {
  24.         //kth smallest in range [l,r]
  25.         if (l > r) return 0;
  26.         if (high == low) return low;
  27.         int left = b[r] - b[l - 1];
  28.         int lb = b[l - 1],rb = b[r];
  29.         if (k <= left) return this->l->kth(lb + 1,rb,k);
  30.         return this->r->kth(l - lb,r - rb,k-left);
  31.     }
  32.     int LTE (int l,int r,int k) {
  33.         //Number of elements in subarray A[L...R] that are less than or equal to y.
  34.         if (l > r or k < low) return 0;
  35.         if (high <= k) return r - l + 1;
  36.         int lb = b[l - 1],rb = b[r];
  37.         return this->l->LTE(lb + 1,rb,k) + this->r->LTE(l - lb,r - rb,k);
  38.     }
  39.     int count (int l,int r,int k) {
  40.         //Number of occurrences of element x in subarray A[L...R].
  41.         if (l > r or k < low or k > high) return 0;
  42.         if (low == high) return r - l + 1;
  43.         int lb = b[l - 1],rb = b[r];
  44.         int mid = low + (high - low) / 2;
  45.         if (k <= mid) return this->l->count(lb + 1,rb,k);
  46.         return this->r->count(l - lb,r - rb,k);
  47.     }
  48.     ~WavletTree () {delete l; delete r;};
  49. };
  50.  
  51. int main () {
  52.      ios::sync_with_stdio(false);
  53.      cin.tie(nullptr);
  54.      cout.tie(nullptr);
  55.      int T = 1;
  56.      //~ cin >> T;
  57.      for (int test_case = 1; test_case <= T; ++test_case) {
  58.          int n;
  59.          cin >> n;
  60.          for (int i = 1; i <= n; ++i) cin >> a[i];
  61.          WavletTree T(a + 1,a + n + 1,1,10000);
  62.          cout << T.LTE(2,6,4) << '\n';
  63.      }
  64.      //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
  65. }
  66.  
RAW Paste Data