diff options
| author | Noobie99 <noob999noob999@gmail.com> | 2023-04-05 23:26:13 +0200 |
|---|---|---|
| committer | Noobie99 <noob999noob999@gmail.com> | 2023-04-05 23:26:13 +0200 |
| commit | 799d0212b6cd222ab78ba3a4a63f867f1bb9c143 (patch) | |
| tree | 58a87f38bbefc2951d68c3627ec3c14a476cc91a | |
| parent | 5823edfb6b3fe8ea8b1e8e3e4a5cbdad2280bfcd (diff) | |
fix spacing + always calc b
| -rw-r--r-- | datastructures/waveletTree.cpp | 8 | ||||
| -rw-r--r-- | tcr.pdf | bin | 669245 -> 669234 bytes |
2 files changed, 4 insertions, 4 deletions
diff --git a/datastructures/waveletTree.cpp b/datastructures/waveletTree.cpp index c211b0f..476658e 100644 --- a/datastructures/waveletTree.cpp +++ b/datastructures/waveletTree.cpp @@ -8,12 +8,12 @@ struct WaveletTree { WaveletTree(it from, it to) : // call above one lo(*min_element(from, to)), hi(*max_element(from, to) + 1) { - if (lo + 1 >= hi) return; ll mid = (lo + hi) / 2; - auto f = [&](ll x){return x < mid;}; + auto f = [&](ll x) {return x < mid;}; for (it c = from; c != to; c++) { b.push_back(b.back() + f(*c)); } + if (lo + 1 >= hi) return; it pivot = stable_partition(from, to, f); ln = new WaveletTree(from, pivot); rn = new WaveletTree(pivot, to); @@ -32,8 +32,8 @@ struct WaveletTree { int countSmaller(int l, int r, ll k) { if (l >= r || k <= lo) return 0; if (hi <= k) return r - l; - return ln->countSmaller(b[l], b[r], k) + - rn->countSmaller(l-b[l], r-b[r], k); + return ln->countSmaller(b[l], b[r], k) + + rn->countSmaller(l-b[l], r-b[r], k); } ~WaveletTree() {delete ln; delete rn;} Binary files differ |
