code":"#ifndef BST_BASE_HH\r\n#define BST_BASE_HH\r\n\r\n#include\r\n#include\r\n#include\r\n\r\nusing i8 = signed char;\r\nusing i64 = long long;\r\nusing u64 = unsigned long long;\r\nusing usize = std::size_t;\r\ntemplate\r\nusing Box = std::unique_ptr;\r\ntemplate\r\nusing Rc = std::shared_ptr;\r\ntemplate\r\nusing Arr = std::array;\r\ntemplate\r\nusing Option = std::optional;\r\n\r\n#define LEN(P) ((P)? (P)->len: 0)\r\n\r\ntemplate class Ptr, typename Node>\r\nNode *bst_find(Ptr &self, decltype(Node::key) const &x){\r\n Node *res = self.get(); // peek but not own the pointer\r\n while(res){ // end the loop if not found\r\n auto const &k = res->key;\r\n if(x == k){\r\n break;\r\n }\r\n res = res->ch[x>k].get(); // when x > k, find x in the right subtree (res->ch[1]); otherwise, find x in the left subtree (res->ch[0])\r\n }\r\n return res;\r\n}\r\n\r\ntemplate class Ptr, typename Node>\r\nNode *bt_nth(Ptr &self, usize n){\r\n if(n >= LEN(self)){ // n's too large; return NIL\r\n return {};\r\n }\r\n Node *res = self.get();\r\n while(1){\r\n if(n < LEN(res->ch[0])){ // n is smaller than the size of the left subtree\r\n res = res->ch[0].get();\r\n continue;\r\n }\r\n n -= LEN(res->ch[0]); // n is at least as large as the size of the left subtree (LEN(res->ch[0])); subtract LEN(res->ch[0]) from n\r\n if(n == 0){ // after the subtraction n becomes 0, so res is the nth element\r\n return res;\r\n }\r\n --n; res = res->ch[1].get(); // n is larger than the size of the union of the root and its left subtree, so the nth element lies in the right subtree (res->ch[1])\r\n }\r\n}\r\n\r\ntemplate class Ptr, typename Node>\r\nNode *bt_first(Ptr &self){\r\n Node *res = self.get();\r\n while(res->ch[0]){\r\n res = res->ch[0].get(); // go left\r\n }\r\n return res;\r\n}\r\n\r\ntemplate class Ptr, typename Node>\r\nNode *bt_last(Ptr &self){\r\n Node *res = self.get();\r\n while(res->ch[1]){\r\n res = res->ch[1].get(); // go right\r\n }\r\n return res;\r\n}\r\n\r\ntemplate class Ptr, typename Node>\r\nArr bst_lower_bound(Ptr &self, decltype(Node::key) const &x){\r\n Arr res{};\r\n Node *it = self.get();\r\n while(it){\r\n auto const &k = it->key;\r\n res[x<=k] = it; // when x <= k, the next (res[1]) is at most it; when x > k, the prev (res[0]) is at least it\r\n it = it->ch[x>k].get(); // when x > k, go right (it->ch[1]); when x <= k, go left (it->ch[0])\r\n }\r\n return res;\r\n}\r\n\r\ntemplate class Ptr, typename Node>\r\nArr bst_upper_bound(Ptr &self, decltype(Node::key) const &x){\r\n Arr res{};\r\n Node *it = self.get();\r\n while(it){\r\n auto const &k = it->key;\r\n res[x= k, the prev (res[0]) is at least it\r\n it = it->ch[x>=k].get(); // when x >= k, go right (it->ch[1]); when x < k, go left (it->ch[0])\r\n }\r\n return res;\r\n}\r\n\r\ntemplate class Ptr, typename Node>\r\nusize bst_rank(Ptr const &self, decltype(Node::key) const &x){\r\n usize res = 0;\r\n Node *it = self.get();\r\n while(it){\r\n if(x <= it->key){ // when x <= the current key, go left\r\n it = it->ch[0].get();\r\n }else{ // otherwise, go right\r\n res += LEN(it->ch[0])+1; // x at least exceeds this many elements\r\n it = it->ch[1].get();\r\n }\r\n }\r\n return res;\r\n}\r\n\r\ntemplate class Ptr, typename Node>\r\nNode *bst_prev(Ptr &self, Node *it){ // REQUIRE: unique keys\r\n return bst_lower_bound(self, it->key)[0]; // if keys are unique, we have lower_bound[1] = it, so the predecessor is lower_bound[0]\r\n}\r\n\r\ntemplate class Ptr, typename Node>\r\nNode *bst_next(Ptr &self, Node *it){ // REQUIRE: unique keys\r\n return bst_upper_bound(self, it->key)[1]; // if keys are unique, we have upper_bound[0] = it, so the successor is upper_bound[1]\r\n}\r\n\r\ntemplate class Ptr, typename Node>\r\nbool ordset_verify(Ptr const &self, decltype(Node::key) const *&ppk){ // verify if self is a valid ordered set; ppk (Pointer to the Predecessor's Key) is passed by reference\r\n if(!self){ // empty set\r\n return true;\r\n }\r\n if(!ordset_verify(self->ch[0], ppk)){ // the left subtree is invalid\r\n return false;\r\n }\r\n if(ppk && *ppk>self->key){ // the predecessor's key > self's key; invalid\r\n return false;\r\n }\r\n return ordset_verify(self->ch[1], ppk=&self->key); // let ppk point to self's key and check if the right subtree is valid\r\n}\r\n\r\ntemplate class Ptr, typename Node>\r\nbool dynset_verify(Ptr const &self){ // verify if self is a valid dynamic set\r\n if(!self){ // empty set\r\n return true;\r\n }\r\n if(self->len != LEN(self->ch[0])+LEN(self->ch[1])+1){ // bad size\r\n return false;\r\n }\r\n return dynset_verify(self->ch[0]) && dynset_verify(self->ch[1]); // verify recursively\r\n}\r\n\r\ntemplate class Ptr, typename Node>\r\nbool bst_verify(Ptr const &self){ // verify if self is a valid BST\r\n decltype(Node::key) const *ppk{}; // Pointer to the Predecessor's Key; initialized to NIL to pass to ordset_verify()\r\n return ordset_verify(self, ppk) && dynset_verify(self); // self is a valid BST iff self is a valid ordered set and is a valid dynamic set\r\n}\r\n\r\n#endif // BST_BASE_HH\r\n\r\n#define BLACK(P) ((P)? (P)->black: true)\r\n#define RED(P) ((P)? !(P)->black: false)\r\nstruct RbNode;\r\nusing Rb = Box;\r\nstruct RbNode{\r\n // constructor\r\n explicit constexpr RbNode(i64 x): key(x){}\r\n // ----------------------------------------------------------\r\n Arr ch; // ch[0]: left subtree, ch[1]: right subtree\r\n i64 const key; // note that key is set to be const and thus cannot be modified after the construction of node\r\n usize len = 1; // the size of subtree rooted at self\r\n bool black = false; // false: RED, true: BLACK\r\n // satellite data (the \"V\" of std::map, optional)\r\n u64 data = 0;\r\n void update() noexcept{\r\n len = LEN(ch[0])+LEN(ch[1])+1;\r\n }\r\n};\r\n\r\nvoid bt_rotate(Rb &self, bool d){ // alike\r\n auto p = std::move(self->ch[d]);\r\n self->ch[d] = std::move(p->ch[!d]);\r\n p->ch[!d] = std::move(self);\r\n self = std::move(p);\r\n self->ch[!d]->update();\r\n self->update();\r\n}\r\n\r\nstd::pair> rbimpl_insert(Rb &self, i64 x){ // return (it, ok(fixme)), where it->key = x and ok indicates whether the insertion takes place (Some(fixme) or None, where fixme indicates whether there're 2 consecutive REDs)\r\n if(!self){ // x doesn't exist in the BST; insertion succeeds\r\n self = Rb(new RbNode(x));\r\n return {self.get(), /*ok=Some*/false};\r\n }\r\n i64 k = self->key;\r\n if(x == k){ // x exists in the BST; insertion fails\r\n return {self.get(), /*ok=None*/{}};\r\n }\r\n bool d = x>=k; // when x >= k, insert x into the right subtree (self->ch[1]); otherwise, insert x into the left subtree (self->ch[0]); when the previous if-clause gets commented out, the seemingly redundant equality allows equivalent keys to be inserted in order\r\n auto [it, ok] = rbimpl_insert(self->ch[d], x);\r\n if(ok){ // x's inserted\r\n self->update(); // update the information of the subtree\r\n if(RED(self) && RED(self->ch[d])){\r\n ok = true; // we can't resolve 2 consecutive REDs if self is not the representative of the node in the corresponding 2--3--4 tree; seek help from the caller (aka parent (must be BLACK)) or the user (set to BLACK manually)\r\n }else if(*ok){ // the RED child owns another RED child\r\n if(RED(self->ch[!d])){ // self becomes a 5-node; split the 5-node into a single RED with one 2-node child and one 3-node child\r\n self->ch[0]->black = self->ch[1]->black = true;\r\n self->black = false;\r\n }else{ // self becomes a 4-node; rotate to make the 4-node valid\r\n if(bool d2=x>=self->ch[d]->key; d!=d2){\r\n bt_rotate(self->ch[d], d2);\r\n }\r\n bt_rotate(self, d);\r\n self->ch[!d]->black = false;\r\n self->black = true;\r\n }\r\n ok = false; // resolved, either temporarily (i.e., self becomes RED) or permanently (i.e., self stays BLACK)\r\n }\r\n }\r\n return {it, ok};\r\n}\r\nstd::pair rb_insert(Rb &self, i64 x){ // return (it, ok), where it->key = x and ok indicates whether the insertion takes place\r\n auto [it, ok] = rbimpl_insert(self, x);\r\n self->black = true; // the root is always BLACK\r\n return {it, ok.has_value()};\r\n}\r\n\r\nbool rbimpl_erase_fixup(Rb *pself, bool d){ // REQUIRE: bh(self->ch[d]) = bh(self->ch[!d])-1 and self->ch[d] is BLACK; make self a valid rb tree (except for the restriction of the root color) and return whether bh decrements; the pointer to self is needed in this case, but sadly this is a reserved keyword...\r\n if(RED((*pself)->ch[!d])){ // the sibling is actually the parent in the corresponding 2--3--4 tree; rotate once to make the sibling a real sibling\r\n bt_rotate(*pself, !d);\r\n (*pself)->ch[d]->black = false;\r\n (*pself)->black = true;\r\n pself = &(*pself)->ch[d];\r\n } // now self->ch[!d] is a real sibling\r\n if(Rb &p=(*pself)->ch[!d]; BLACK(p->ch[!d])){\r\n if(BLACK(p->ch[d])){ // p is a 2-node; pair self and p to create a 3-node\r\n p->black = false;\r\n if(RED(*pself)){ // self is not a representative of a node in the corresponding 2--3--4 tree; we can drag it down with p to create a 3-node\r\n (*pself)->black = true;\r\n return false;\r\n }\r\n return true; // sadly we have no choice but to decrement the bh of the red--black tree\r\n } // p is a 3-node; since we want p->ch[!d] to be RED, replace p with p->ch[d]\r\n bt_rotate(p, d);\r\n p->ch[!d]->black = false;\r\n p->black = true;\r\n } // the sibling is a 3- or 4-node with its !d child being RED\r\n bt_rotate(*pself, !d); // make the sibling the new root\r\n (*pself)->black = (*pself)->ch[d]->black;\r\n (*pself)->ch[0]->black = (*pself)->ch[1]->black = true;\r\n return false;\r\n}\r\nstd::pair rbimpl_pop_end(Rb &end, bool d){ // REQUIRE: end is either first (d=0) or last (d=1) of some subtree; pop end and return (end, fixme), where end is the popped end and fixme indicates whether bh decrements\r\n Rb res = std::move(end);\r\n end = std::move(res->ch[!d]);\r\n bool fixme = false;\r\n if(RED(end)){ // make the new end BLACK\r\n end->black = true;\r\n }else{ // if popped end is BLACK, we seek help from the caller\r\n fixme = BLACK(res);\r\n }\r\n return {std::move(res), fixme};\r\n}\r\nstd::pair rbimpl_pop_first(Rb &self){ // REQUIRE: non-empty; return (p, fixme), where p is the first node and fixme indicates whether bh decrements\r\n if(!self->ch[0]){ // self doesn't have a left child, so self is the first of some subtree\r\n return rbimpl_pop_end(self, 0);\r\n }\r\n auto [res, fixme] = rbimpl_pop_first(self->ch[0]); // otherwise, go left\r\n self->update();\r\n if(fixme){ // bh(self->ch[0]) = bh(self->ch[1])-1\r\n fixme = rbimpl_erase_fixup(&self, 0);\r\n }\r\n return {std::move(res), fixme};\r\n}\r\nstd::pair rbimpl_erase(Rb &self, i64 x){ // return (count, fixme), whether count is the number of erased elements (1 or 0 in this case) and fixme indicates whether bh decrements\r\n if(!self){ // x not found\r\n return {/*count=*/0, /*fixme=*/false};\r\n }\r\n if(i64 k=self->key; x != k){ // not this node\r\n auto [res, fixme] = rbimpl_erase(self->ch[x>k], x); // when x > k, find x in the right subtree (self->ch[1]); otherwise, find x in the left subtree (self->ch[0])\r\n self->update(); // update the information of the subtree; if update() and fixup() are expensive, consider checking res first\r\n if(fixme){ // bh(self->ch[x>k]) = bh(self->ch[xk);\r\n }\r\n return {res, fixme};\r\n }\r\n for(bool d: {0, 1}) if(!self->ch[d]){ // if either child is NIL, let the other replace the position of self\r\n auto [_, fixme] = rbimpl_pop_end(self, d);\r\n return {/*count=*/1, fixme};\r\n } // neither the left nor the right subtree is empty; let the successor replace the position of self\r\n auto [y, fixme] = rbimpl_pop_first(self->ch[1]); // y: successor of self\r\n y->ch = {std::move(self->ch[0]), std::move(self->ch[1])}; // self's children becomes y's\r\n y->black = self->black; // self's color becomes y's\r\n self = std::move(y); // old self gets freed automatically\r\n self->update();\r\n if(fixme){ // bh(self->ch[1]) = bh(self->ch[0])-1\r\n fixme = rbimpl_erase_fixup(&self, 1);\r\n }\r\n return {/*count=*/1, fixme};\r\n}\r\nusize rb_erase(Rb &self, i64 x){ // return the number of erased elements; it's always 1 or 0\r\n auto [res, _] = rbimpl_erase(self, x); // we don't care whether bh decrements or not\r\n return res;\r\n}\r\n\r\nbool rbimpl_bh_verify(Rb const &self, Option &bh, int h){ // verify if the colors of nodes in self are valid\r\n if(!self){ // NIL leaf\r\n if(!bh){ // bh is None; set bh to Some(h)\r\n bh = h;\r\n return true;\r\n } // otherwise, check if h = bh\r\n return h == bh;\r\n }\r\n if(RED(self) && (RED(self->ch[0]) || RED(self->ch[1]))){ // 2 consecutive REDs\r\n return false;\r\n }\r\n return rbimpl_bh_verify(self->ch[0], bh, h+BLACK(self)) && rbimpl_bh_verify(self->ch[1], bh, h+BLACK(self));\r\n}\r\nbool rb_verify(Rb const &self){ // verify if self is a valid red--black tree\r\n if(!bst_verify(self) || RED(self)){ // the root should always be BLACK\r\n return false;\r\n }\r\n Option bh; // the black height of self; initialized to None to pass to rbimpl_bh_verify()\r\n return rbimpl_bh_verify(self, bh, 0);\r\n}\r\n\r\n#include\r\n#include\r\n#include\r\n#include\r\nnamespace chrono = std::chrono;\r\n\r\nint main(){\r\n constexpr int N = 1'000'000;\r\n std::mt19937_64 Rng(58);\r\n auto tick = chrono::steady_clock::now();\r\n Rb bst;\r\n for(int i=N; i>=1; --i){\r\n rb_insert(bst, i);\r\n }\r\n std::puts(rb_verify(bst)? \"Expected\": \"What?!\");\r\n std::printf(\"%zu\\n\", LEN(bst));\r\n for(int i=1; i<=N; ++i){\r\n int r = std::uniform_int_distribution<>(1, N)(Rng);\r\n rb_erase(bst, r);\r\n }\r\n std::puts(rb_verify(bst)? \"Expected\": \"What?!\");\r\n std::printf(\"%zu\\n\", LEN(bst));\r\n auto tock = chrono::steady_clock::now();\r\n std::printf(\"Time Elapsed: %.3fs\\n\", chrono::duration(tock-tick).count());\r\n}\r\n","file_name":"main.cpp","active":1}]

Onlinecpp_slow