src/ds/bst/fhq/lib.hpp - GCC Code Coverage Report

Directory:	./
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	100.0%	205 / 0 / 205
Functions:	100.0%	37 / 0 / 37
Branches:	89.5%	111 / 0 / 124

    src/ds/bst/fhq/lib.hpp
    
        Line
        Branch
        Exec
        Source
      
        #pragma once
      
        #include "../../../util/alias/others/lib.hpp"
      
        #include "../../../util/rand/lib.hpp"
      
        namespace tifa_libs {
      
        template <class T, bool recovery = false, class Comp = std::less<T>>
      
        struct fhq_treap {
      
          static CEXP Comp compare{};
      
          struct TIFA {
      
            T val;
      
            // NOLINTNEXTLINE(modernize-avoid-c-arrays)
      
            u32 r, sz, son[2];
      
          };
      
          rand_gen<u32> rnd;
      
          vec<TIFA> data{1};
      
          vecu stk;
      
          u32 root{};
      
         private:
      
        17044656
          CEXP u32 new_node(cT_(T) val) NE {
      
            u32 ret;
      
            if CEXP (recovery) {
      
              if (stk.size()) data[ret = stk.back()] = {val, rnd(), 1, {0, 0}}, stk.pop_back();
      
              else ret = (u32)data.size(), data.push_back(TIFA{val, rnd(), 1, {0, 0}});
      
        17044656
            } else ret = (u32)data.size(), data.push_back(TIFA{val, rnd(), 1, {0, 0}});
      
        17044656
            return ret;
      
          }
      
        315021353
          CEXP void pushup(u32 pos) NE { data[pos].sz = data[data[pos].son[0]].sz + 1 + data[data[pos].son[1]].sz; }
      
          template <bool strict = false>
      
        31048870
          CEXP pttu split_root(u32 pos, cT_(T) key) NE {
      
          6/6std::pair<unsigned int, unsigned int> tifa_libs::fhq_treap<int, false, std::less<int> >::split_root<true>(unsigned int, int):
✓ Branch 0 taken 121396 times.
✓ Branch 1 taken 363113 times.
std::pair<unsigned int, unsigned int> tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::split_root<true>(unsigned int, std::pair<unsigned long, unsigned long>):
✓ Branch 0 taken 4548684 times.
✓ Branch 1 taken 12078948 times.
std::pair<unsigned int, unsigned int> tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::split_root<true>(unsigned int, unsigned int):
✓ Branch 0 taken 4498980 times.
✓ Branch 1 taken 9437749 times.

        31048870
            if (!pos) return {};
      
            bool f;
      
        21879810
            if CEXP (strict) f = compare(data[pos].val, key);
      
            else f = !compare(key, data[pos].val);
      
          6/6std::pair<unsigned int, unsigned int> tifa_libs::fhq_treap<int, false, std::less<int> >::split_root<true>(unsigned int, int):
✓ Branch 0 taken 181623 times.
✓ Branch 1 taken 181490 times.
std::pair<unsigned int, unsigned int> tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::split_root<true>(unsigned int, std::pair<unsigned long, unsigned long>):
✓ Branch 0 taken 7345996 times.
✓ Branch 1 taken 4732952 times.
std::pair<unsigned int, unsigned int> tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::split_root<true>(unsigned int, unsigned int):
✓ Branch 0 taken 8721760 times.
✓ Branch 1 taken 715989 times.

        21879810
            if (f) {
      
        16249379
              auto [l, r] = split_root<strict>(data[pos].son[1], key);
      
        16249379
              data[pos].son[1] = l, pushup(pos);
      
        16249379
              return {pos, r};
      
            }
      
        5630431
            auto [l, r] = split_root<strict>(data[pos].son[0], key);
      
        5630431
            data[pos].son[0] = r, pushup(pos);
      
        5630431
            return {l, pos};
      
          }
      
        4976740
          CEXP u32 merge_root(u32 l, u32 r) NE {
      
          6/6tifa_libs::fhq_treap<int, false, std::less<int> >::merge_root(unsigned int, unsigned int):
✓ Branch 0 taken 36651 times.
✓ Branch 1 taken 38068 times.
tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::merge_root(unsigned int, unsigned int):
✓ Branch 0 taken 2151443 times.
✓ Branch 1 taken 1410782 times.
tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::merge_root(unsigned int, unsigned int):
✓ Branch 0 taken 737304 times.
✓ Branch 1 taken 602492 times.

        4976740
            if (!l | !r) return l | r;
      
          6/6tifa_libs::fhq_treap<int, false, std::less<int> >::merge_root(unsigned int, unsigned int):
✓ Branch 2 taken 18965 times.
✓ Branch 3 taken 19103 times.
tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::merge_root(unsigned int, unsigned int):
✓ Branch 2 taken 704845 times.
✓ Branch 3 taken 705937 times.
tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::merge_root(unsigned int, unsigned int):
✓ Branch 2 taken 301307 times.
✓ Branch 3 taken 301185 times.

        2051342
            if (data[l].r < data[r].r) {
      
        1025117
              data[l].son[1] = merge_root(data[l].son[1], r), pushup(l);
      
        1025117
              return l;
      
            }
      
        1026225
            data[r].son[0] = merge_root(l, data[r].son[0]), pushup(r);
      
        1026225
            return r;
      
          }
      
         public:
      
          3/6tifa_libs::fhq_treap<int, false, std::less<int> >::fhq_treap():
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::fhq_treap():
✓ Branch 4 taken 20 times.
✗ Branch 5 not taken.
tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::fhq_treap():
✓ Branch 4 taken 37 times.
✗ Branch 5 not taken.

        201
          CEXP fhq_treap() : rnd{}, stk{} { data[0].sz = {}; }
      
        17044656
          CEXP void insert(cT_(T) val) NE {
      
        17044656
            u32 tar = new_node(val);
      
        272209589
            auto dfs = [&](auto&& f, u32& pos) NE -> void {
      
          6/6void tifa_libs::fhq_treap<int, false, std::less<int> >::insert(int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 0 taken 59867 times.
✓ Branch 1 taken 3031517 times.
void tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::insert(std::pair<unsigned long, unsigned long>)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 0 taken 3476595 times.
✓ Branch 1 taken 132363159 times.
void tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::insert(unsigned int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 0 taken 4339134 times.
✓ Branch 1 taken 111894661 times.

        255164933
              if (!pos) return void(pos = tar);
      
          6/6void tifa_libs::fhq_treap<int, false, std::less<int> >::insert(int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 2 taken 121396 times.
✓ Branch 3 taken 2910121 times.
void tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::insert(std::pair<unsigned long, unsigned long>)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 2 taken 4548684 times.
✓ Branch 3 taken 127814475 times.
void tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::insert(unsigned int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 2 taken 4498980 times.
✓ Branch 3 taken 107395681 times.

        247289337
              if (data[tar].r < data[pos].r) {
      
        9169060
                auto [l, r] = split_root<true>(pos, val);
      
        9169060
                data[tar].son[0] = l, data[tar].son[1] = r;
      
        9169060
                pos = tar;
      
          6/6void tifa_libs::fhq_treap<int, false, std::less<int> >::insert(int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 2 taken 1433764 times.
✓ Branch 3 taken 1476357 times.
void tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::insert(std::pair<unsigned long, unsigned long>)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 2 taken 74753313 times.
✓ Branch 3 taken 53061162 times.
void tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::insert(unsigned int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 2 taken 100051463 times.
✓ Branch 3 taken 7344218 times.

        238120277
              } else f(f, compare(data[pos].val, val) ? data[pos].son[1] : data[pos].son[0]);
      
        247289337
              pushup(pos);
      
            };
      
        17044656
            dfs(dfs, root);
      
        17044656
          }
      
        2925398
          CEXP bool erase(cT_(T) val) NE {
      
        49651660
            auto dfs = [&](auto&& f, u32& pos) NE -> bool {
      
          3/6bool tifa_libs::fhq_treap<int, false, std::less<int> >::erase(int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 624290 times.
bool tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::erase(std::pair<unsigned long, unsigned long>)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 33097179 times.
bool tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::erase(unsigned int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 13004793 times.

        46726262
              if (!pos) return false;
      
          6/6bool tifa_libs::fhq_treap<int, false, std::less<int> >::erase(int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 1 taken 36651 times.
✓ Branch 2 taken 587639 times.
bool tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::erase(std::pair<unsigned long, unsigned long>)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 2 taken 2151443 times.
✓ Branch 3 taken 30945736 times.
bool tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::erase(unsigned int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 1 taken 737304 times.
✓ Branch 2 taken 12267489 times.

        46726262
              if (data[pos].val == val) {
      
                if CEXP (recovery) stk.push_back(pos);
      
        2925398
                pos = merge_root(data[pos].son[0], data[pos].son[1]);
      
        2925398
                return true;
      
              }
      
          9/12bool tifa_libs::fhq_treap<int, false, std::less<int> >::erase(int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 2 taken 289374 times.
✓ Branch 3 taken 298265 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 587639 times.
bool tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::erase(std::pair<unsigned long, unsigned long>)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 2 taken 11386945 times.
✓ Branch 3 taken 19558791 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 30945736 times.
bool tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::erase(unsigned int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const:
✓ Branch 2 taken 6112312 times.
✓ Branch 3 taken 6155177 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 12267489 times.

        43800864
              if (!f(f, compare(data[pos].val, val) ? data[pos].son[1] : data[pos].son[0])) return false;
      
        43800864
              pushup(pos);
      
        43800864
              return true;
      
            };
      
        2925398
            return dfs(dfs, root);
      
          }
      
        17500021
          ND CEXP auto find(cT_(T) val) CNE {
      
        17500021
            u32 pos = root;
      
          2/2✓ Branch 0 taken 244757422 times.
✓ Branch 1 taken 11983968 times.

        256741390
            while (pos)
      
          2/2✓ Branch 1 taken 5516053 times.
✓ Branch 2 taken 239241369 times.

        244757422
              if (val == data[pos].val) return data.cbegin() + pos;
      
        239241369
              else pos = data[pos].son[!compare(val, data[pos].val)];
      
        11983968
            return data.cend();
      
          }
      
        3017909
          ND CEXP u32 rank(cT_(T) val) CNE {
      
        3017909
            u32 pos = root, res = 0;
      
          4/4tifa_libs::fhq_treap<int, false, std::less<int> >::rank(int) const:
✓ Branch 0 taken 647529 times.
✓ Branch 1 taken 35837 times.
tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::rank(unsigned int) const:
✓ Branch 0 taken 44914010 times.
✓ Branch 1 taken 2982072 times.

        48579448
            while (pos)
      
          4/4tifa_libs::fhq_treap<int, false, std::less<int> >::rank(int) const:
✓ Branch 2 taken 319374 times.
✓ Branch 3 taken 328155 times.
tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::rank(unsigned int) const:
✓ Branch 2 taken 22466640 times.
✓ Branch 3 taken 22447370 times.

        45561539
              if (compare(data[pos].val, val)) res += data[data[pos].son[0]].sz + 1, pos = data[pos].son[1];
      
        22775525
              else pos = data[pos].son[0];
      
        3017909
            return res + 1;
      
          }
      
          ND CEXP u32 count(cT_(T) val) CNE {
      
            u32 rk = rank(val);
      
            if (auto res = next(val); !res) return data[root].sz - rk + 1;
      
            else return rank(res.value()) - rk;
      
          }
      
        3018595
          ND CEXP auto kth(u32 k) CNE {
      
        3018595
            std::optional<T> ret;
      
          8/12tifa_libs::fhq_treap<int, false, std::less<int> >::kth(unsigned int) const:
✓ Branch 0 taken 36872 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 36872 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 36872 times.
tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::kth(unsigned int) const:
✓ Branch 0 taken 2981723 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 154578 times.
✓ Branch 4 taken 2827145 times.
✓ Branch 5 taken 154578 times.
✓ Branch 6 taken 2827145 times.

        3018595
            if (k < 1 || k > data[root].sz) return ret;
      
        2864017
            u32 pos = root;
      
        45578299
            while (true)
      
          4/4tifa_libs::fhq_treap<int, false, std::less<int> >::kth(unsigned int) const:
✓ Branch 3 taken 36872 times.
✓ Branch 4 taken 592340 times.
tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::kth(unsigned int) const:
✓ Branch 3 taken 2827145 times.
✓ Branch 4 taken 44985959 times.

        48442316
              if (auto _ = data[pos].sz - data[data[pos].son[1]].sz; _ == k) {
      
        2864017
                ret.emplace(data[pos].val);
      
        2864017
                return ret;
      
          4/4tifa_libs::fhq_treap<int, false, std::less<int> >::kth(unsigned int) const:
✓ Branch 0 taken 291818 times.
✓ Branch 1 taken 300522 times.
tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::kth(unsigned int) const:
✓ Branch 0 taken 22740738 times.
✓ Branch 1 taken 22245221 times.

        45578299
              } else if (_ < k) k -= _, pos = data[pos].son[1];
      
        22545743
              else pos = data[pos].son[0];
      
          }
      
        17834434
          ND CEXP auto prev(cT_(T) val) CNE {
      
        17834434
            u32 pos = root;
      
        17834434
            std::optional<T> ret;
      
          6/6tifa_libs::fhq_treap<int, false, std::less<int> >::prev(int) const:
✓ Branch 0 taken 638148 times.
✓ Branch 1 taken 35430 times.
tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::prev(std::pair<unsigned long, unsigned long>) const:
✓ Branch 0 taken 269156539 times.
✓ Branch 1 taken 15673163 times.
tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::prev(unsigned int) const:
✓ Branch 0 taken 31248200 times.
✓ Branch 1 taken 2125841 times.

        318877321
            while (pos)
      
          6/6tifa_libs::fhq_treap<int, false, std::less<int> >::prev(int) const:
✓ Branch 2 taken 321358 times.
✓ Branch 3 taken 316790 times.
tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::prev(std::pair<unsigned long, unsigned long>) const:
✓ Branch 2 taken 113141100 times.
✓ Branch 3 taken 156015439 times.
tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::prev(unsigned int) const:
✓ Branch 2 taken 15258649 times.
✓ Branch 3 taken 15989551 times.

        301042887
              if (!compare(data[pos].val, val)) pos = data[pos].son[0];
      
        172321780
              else ret.emplace(data[pos].val), pos = data[pos].son[1];
      
        17834434
            return ret;
      
          }
      
        2155574
          ND CEXP auto next(cT_(T) val) CNE {
      
        2155574
            u32 pos = root;
      
        2155574
            std::optional<T> ret;
      
          4/4tifa_libs::fhq_treap<int, false, std::less<int> >::next(int) const:
✓ Branch 0 taken 631173 times.
✓ Branch 1 taken 35127 times.
tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::next(unsigned int) const:
✓ Branch 0 taken 31242843 times.
✓ Branch 1 taken 2120447 times.

        34029590
            while (pos)
      
          4/4tifa_libs::fhq_treap<int, false, std::less<int> >::next(int) const:
✓ Branch 2 taken 309697 times.
✓ Branch 3 taken 321476 times.
tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::next(unsigned int) const:
✓ Branch 2 taken 15669321 times.
✓ Branch 3 taken 15573522 times.

        31874016
              if (!compare(val, data[pos].val)) pos = data[pos].son[1];
      
        15894998
              else ret.emplace(data[pos].val), pos = data[pos].son[0];
      
        2155574
            return ret;
      
          }
      
        };
      
        }  // namespace tifa_libs

Line	Branch	Exec	Source
1			#pragma once
2
3			#include "../../../util/alias/others/lib.hpp"
4			#include "../../../util/rand/lib.hpp"
5
6			namespace tifa_libs {
7
8			template <class T, bool recovery = false, class Comp = std::less<T>>
9			struct fhq_treap {
10			static CEXP Comp compare{};
11			struct TIFA {
12			T val;
13			// NOLINTNEXTLINE(modernize-avoid-c-arrays)
14			u32 r, sz, son[2];
15			};
16			rand_gen<u32> rnd;
17			vec<TIFA> data{1};
18			vecu stk;
19			u32 root{};
20
21			private:
22		17044656	CEXP u32 new_node(cT_(T) val) NE {
23			u32 ret;
24			if CEXP (recovery) {
25			if (stk.size()) data[ret = stk.back()] = {val, rnd(), 1, {0, 0}}, stk.pop_back();
26			else ret = (u32)data.size(), data.push_back(TIFA{val, rnd(), 1, {0, 0}});
27		17044656	} else ret = (u32)data.size(), data.push_back(TIFA{val, rnd(), 1, {0, 0}});
28		17044656	return ret;
29			}
30		315021353	CEXP void pushup(u32 pos) NE { data[pos].sz = data[data[pos].son[0]].sz + 1 + data[data[pos].son[1]].sz; }
31			template <bool strict = false>
32		31048870	CEXP pttu split_root(u32 pos, cT_(T) key) NE {
33	6/6 std::pair<unsigned int, unsigned int> tifa_libs::fhq_treap<int, false, std::less<int> >::split_root<true>(unsigned int, int): ✓ Branch 0 taken 121396 times. ✓ Branch 1 taken 363113 times. std::pair<unsigned int, unsigned int> tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::split_root<true>(unsigned int, std::pair<unsigned long, unsigned long>): ✓ Branch 0 taken 4548684 times. ✓ Branch 1 taken 12078948 times. std::pair<unsigned int, unsigned int> tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::split_root<true>(unsigned int, unsigned int): ✓ Branch 0 taken 4498980 times. ✓ Branch 1 taken 9437749 times.	31048870	if (!pos) return {};
34			bool f;
35		21879810	if CEXP (strict) f = compare(data[pos].val, key);
36			else f = !compare(key, data[pos].val);
37	6/6 std::pair<unsigned int, unsigned int> tifa_libs::fhq_treap<int, false, std::less<int> >::split_root<true>(unsigned int, int): ✓ Branch 0 taken 181623 times. ✓ Branch 1 taken 181490 times. std::pair<unsigned int, unsigned int> tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::split_root<true>(unsigned int, std::pair<unsigned long, unsigned long>): ✓ Branch 0 taken 7345996 times. ✓ Branch 1 taken 4732952 times. std::pair<unsigned int, unsigned int> tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::split_root<true>(unsigned int, unsigned int): ✓ Branch 0 taken 8721760 times. ✓ Branch 1 taken 715989 times.	21879810	if (f) {
38		16249379	auto [l, r] = split_root<strict>(data[pos].son[1], key);
39		16249379	data[pos].son[1] = l, pushup(pos);
40		16249379	return {pos, r};
41			}
42		5630431	auto [l, r] = split_root<strict>(data[pos].son[0], key);
43		5630431	data[pos].son[0] = r, pushup(pos);
44		5630431	return {l, pos};
45			}
46		4976740	CEXP u32 merge_root(u32 l, u32 r) NE {
47	6/6 tifa_libs::fhq_treap<int, false, std::less<int> >::merge_root(unsigned int, unsigned int): ✓ Branch 0 taken 36651 times. ✓ Branch 1 taken 38068 times. tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::merge_root(unsigned int, unsigned int): ✓ Branch 0 taken 2151443 times. ✓ Branch 1 taken 1410782 times. tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::merge_root(unsigned int, unsigned int): ✓ Branch 0 taken 737304 times. ✓ Branch 1 taken 602492 times.	4976740	if (!l \| !r) return l \| r;
48	6/6 tifa_libs::fhq_treap<int, false, std::less<int> >::merge_root(unsigned int, unsigned int): ✓ Branch 2 taken 18965 times. ✓ Branch 3 taken 19103 times. tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::merge_root(unsigned int, unsigned int): ✓ Branch 2 taken 704845 times. ✓ Branch 3 taken 705937 times. tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::merge_root(unsigned int, unsigned int): ✓ Branch 2 taken 301307 times. ✓ Branch 3 taken 301185 times.	2051342	if (data[l].r < data[r].r) {
49		1025117	data[l].son[1] = merge_root(data[l].son[1], r), pushup(l);
50		1025117	return l;
51			}
52		1026225	data[r].son[0] = merge_root(l, data[r].son[0]), pushup(r);
53		1026225	return r;
54			}
55
56			public:
57	3/6 tifa_libs::fhq_treap<int, false, std::less<int> >::fhq_treap(): ✓ Branch 4 taken 10 times. ✗ Branch 5 not taken. tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::fhq_treap(): ✓ Branch 4 taken 20 times. ✗ Branch 5 not taken. tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::fhq_treap(): ✓ Branch 4 taken 37 times. ✗ Branch 5 not taken.	201	CEXP fhq_treap() : rnd{}, stk{} { data[0].sz = {}; }
58		17044656	CEXP void insert(cT_(T) val) NE {
59		17044656	u32 tar = new_node(val);
60		272209589	auto dfs = [&](auto&& f, u32& pos) NE -> void {
61	6/6 void tifa_libs::fhq_treap<int, false, std::less<int> >::insert(int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 0 taken 59867 times. ✓ Branch 1 taken 3031517 times. void tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::insert(std::pair<unsigned long, unsigned long>)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 0 taken 3476595 times. ✓ Branch 1 taken 132363159 times. void tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::insert(unsigned int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 0 taken 4339134 times. ✓ Branch 1 taken 111894661 times.	255164933	if (!pos) return void(pos = tar);
62	6/6 void tifa_libs::fhq_treap<int, false, std::less<int> >::insert(int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 2 taken 121396 times. ✓ Branch 3 taken 2910121 times. void tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::insert(std::pair<unsigned long, unsigned long>)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 2 taken 4548684 times. ✓ Branch 3 taken 127814475 times. void tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::insert(unsigned int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 2 taken 4498980 times. ✓ Branch 3 taken 107395681 times.	247289337	if (data[tar].r < data[pos].r) {
63		9169060	auto [l, r] = split_root<true>(pos, val);
64		9169060	data[tar].son[0] = l, data[tar].son[1] = r;
65		9169060	pos = tar;
66	6/6 void tifa_libs::fhq_treap<int, false, std::less<int> >::insert(int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 2 taken 1433764 times. ✓ Branch 3 taken 1476357 times. void tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::insert(std::pair<unsigned long, unsigned long>)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 2 taken 74753313 times. ✓ Branch 3 taken 53061162 times. void tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::insert(unsigned int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 2 taken 100051463 times. ✓ Branch 3 taken 7344218 times.	238120277	} else f(f, compare(data[pos].val, val) ? data[pos].son[1] : data[pos].son[0]);
67		247289337	pushup(pos);
68			};
69		17044656	dfs(dfs, root);
70		17044656	}
71		2925398	CEXP bool erase(cT_(T) val) NE {
72		49651660	auto dfs = [&](auto&& f, u32& pos) NE -> bool {
73	3/6 bool tifa_libs::fhq_treap<int, false, std::less<int> >::erase(int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✗ Branch 0 not taken. ✓ Branch 1 taken 624290 times. bool tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::erase(std::pair<unsigned long, unsigned long>)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✗ Branch 0 not taken. ✓ Branch 1 taken 33097179 times. bool tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::erase(unsigned int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✗ Branch 0 not taken. ✓ Branch 1 taken 13004793 times.	46726262	if (!pos) return false;
74	6/6 bool tifa_libs::fhq_treap<int, false, std::less<int> >::erase(int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 1 taken 36651 times. ✓ Branch 2 taken 587639 times. bool tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::erase(std::pair<unsigned long, unsigned long>)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 2 taken 2151443 times. ✓ Branch 3 taken 30945736 times. bool tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::erase(unsigned int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 1 taken 737304 times. ✓ Branch 2 taken 12267489 times.	46726262	if (data[pos].val == val) {
75			if CEXP (recovery) stk.push_back(pos);
76		2925398	pos = merge_root(data[pos].son[0], data[pos].son[1]);
77		2925398	return true;
78			}
79	9/12 bool tifa_libs::fhq_treap<int, false, std::less<int> >::erase(int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 2 taken 289374 times. ✓ Branch 3 taken 298265 times. ✗ Branch 7 not taken. ✓ Branch 8 taken 587639 times. bool tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::erase(std::pair<unsigned long, unsigned long>)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 2 taken 11386945 times. ✓ Branch 3 taken 19558791 times. ✗ Branch 7 not taken. ✓ Branch 8 taken 30945736 times. bool tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::erase(unsigned int)::{lambda(auto:1&&, unsigned int&)#1}::operator()<{lambda(auto:1&&, unsigned int&)#1}&>({lambda(auto:1&&, unsigned int&)#1}&, unsigned int&) const: ✓ Branch 2 taken 6112312 times. ✓ Branch 3 taken 6155177 times. ✗ Branch 7 not taken. ✓ Branch 8 taken 12267489 times.	43800864	if (!f(f, compare(data[pos].val, val) ? data[pos].son[1] : data[pos].son[0])) return false;
80		43800864	pushup(pos);
81		43800864	return true;
82			};
83		2925398	return dfs(dfs, root);
84			}
85		17500021	ND CEXP auto find(cT_(T) val) CNE {
86		17500021	u32 pos = root;
87	2/2 ✓ Branch 0 taken 244757422 times. ✓ Branch 1 taken 11983968 times.	256741390	while (pos)
88	2/2 ✓ Branch 1 taken 5516053 times. ✓ Branch 2 taken 239241369 times.	244757422	if (val == data[pos].val) return data.cbegin() + pos;
89		239241369	else pos = data[pos].son[!compare(val, data[pos].val)];
90		11983968	return data.cend();
91			}
92		3017909	ND CEXP u32 rank(cT_(T) val) CNE {
93		3017909	u32 pos = root, res = 0;
94	4/4 tifa_libs::fhq_treap<int, false, std::less<int> >::rank(int) const: ✓ Branch 0 taken 647529 times. ✓ Branch 1 taken 35837 times. tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::rank(unsigned int) const: ✓ Branch 0 taken 44914010 times. ✓ Branch 1 taken 2982072 times.	48579448	while (pos)
95	4/4 tifa_libs::fhq_treap<int, false, std::less<int> >::rank(int) const: ✓ Branch 2 taken 319374 times. ✓ Branch 3 taken 328155 times. tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::rank(unsigned int) const: ✓ Branch 2 taken 22466640 times. ✓ Branch 3 taken 22447370 times.	45561539	if (compare(data[pos].val, val)) res += data[data[pos].son[0]].sz + 1, pos = data[pos].son[1];
96		22775525	else pos = data[pos].son[0];
97		3017909	return res + 1;
98			}
99			ND CEXP u32 count(cT_(T) val) CNE {
100			u32 rk = rank(val);
101			if (auto res = next(val); !res) return data[root].sz - rk + 1;
102			else return rank(res.value()) - rk;
103			}
104		3018595	ND CEXP auto kth(u32 k) CNE {
105		3018595	std::optional<T> ret;
106	8/12 tifa_libs::fhq_treap<int, false, std::less<int> >::kth(unsigned int) const: ✓ Branch 0 taken 36872 times. ✗ Branch 1 not taken. ✗ Branch 3 not taken. ✓ Branch 4 taken 36872 times. ✗ Branch 5 not taken. ✓ Branch 6 taken 36872 times. tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::kth(unsigned int) const: ✓ Branch 0 taken 2981723 times. ✗ Branch 1 not taken. ✓ Branch 3 taken 154578 times. ✓ Branch 4 taken 2827145 times. ✓ Branch 5 taken 154578 times. ✓ Branch 6 taken 2827145 times.	3018595	if (k < 1 \|\| k > data[root].sz) return ret;
107		2864017	u32 pos = root;
108		45578299	while (true)
109	4/4 tifa_libs::fhq_treap<int, false, std::less<int> >::kth(unsigned int) const: ✓ Branch 3 taken 36872 times. ✓ Branch 4 taken 592340 times. tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::kth(unsigned int) const: ✓ Branch 3 taken 2827145 times. ✓ Branch 4 taken 44985959 times.	48442316	if (auto _ = data[pos].sz - data[data[pos].son[1]].sz; _ == k) {
110		2864017	ret.emplace(data[pos].val);
111		2864017	return ret;
112	4/4 tifa_libs::fhq_treap<int, false, std::less<int> >::kth(unsigned int) const: ✓ Branch 0 taken 291818 times. ✓ Branch 1 taken 300522 times. tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::kth(unsigned int) const: ✓ Branch 0 taken 22740738 times. ✓ Branch 1 taken 22245221 times.	45578299	} else if (_ < k) k -= _, pos = data[pos].son[1];
113		22545743	else pos = data[pos].son[0];
114			}
115		17834434	ND CEXP auto prev(cT_(T) val) CNE {
116		17834434	u32 pos = root;
117		17834434	std::optional<T> ret;
118	6/6 tifa_libs::fhq_treap<int, false, std::less<int> >::prev(int) const: ✓ Branch 0 taken 638148 times. ✓ Branch 1 taken 35430 times. tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::prev(std::pair<unsigned long, unsigned long>) const: ✓ Branch 0 taken 269156539 times. ✓ Branch 1 taken 15673163 times. tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::prev(unsigned int) const: ✓ Branch 0 taken 31248200 times. ✓ Branch 1 taken 2125841 times.	318877321	while (pos)
119	6/6 tifa_libs::fhq_treap<int, false, std::less<int> >::prev(int) const: ✓ Branch 2 taken 321358 times. ✓ Branch 3 taken 316790 times. tifa_libs::fhq_treap<std::pair<unsigned long, unsigned long>, false, std::less<std::pair<unsigned long, unsigned long> > >::prev(std::pair<unsigned long, unsigned long>) const: ✓ Branch 2 taken 113141100 times. ✓ Branch 3 taken 156015439 times. tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::prev(unsigned int) const: ✓ Branch 2 taken 15258649 times. ✓ Branch 3 taken 15989551 times.	301042887	if (!compare(data[pos].val, val)) pos = data[pos].son[0];
120		172321780	else ret.emplace(data[pos].val), pos = data[pos].son[1];
121		17834434	return ret;
122			}
123		2155574	ND CEXP auto next(cT_(T) val) CNE {
124		2155574	u32 pos = root;
125		2155574	std::optional<T> ret;
126	4/4 tifa_libs::fhq_treap<int, false, std::less<int> >::next(int) const: ✓ Branch 0 taken 631173 times. ✓ Branch 1 taken 35127 times. tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::next(unsigned int) const: ✓ Branch 0 taken 31242843 times. ✓ Branch 1 taken 2120447 times.	34029590	while (pos)
127	4/4 tifa_libs::fhq_treap<int, false, std::less<int> >::next(int) const: ✓ Branch 2 taken 309697 times. ✓ Branch 3 taken 321476 times. tifa_libs::fhq_treap<unsigned int, false, std::less<unsigned int> >::next(unsigned int) const: ✓ Branch 2 taken 15669321 times. ✓ Branch 3 taken 15573522 times.	31874016	if (!compare(val, data[pos].val)) pos = data[pos].son[1];
128		15894998	else ret.emplace(data[pos].val), pos = data[pos].son[0];
129		2155574	return ret;
130			}
131			};
132
133			} // namespace tifa_libs
134