# 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