#include #include #include class AVLTree { enum class Bias : char { Left, Right, Equal }; using Key = int; using Value = int; public: AVLTree(const Key &, const Value & = Value{}, const std::shared_ptr & = { nullptr }, const std::shared_ptr & = { nullptr }, const Bias & = Bias::Equal); AVLTree(); void incriment(const Key &); Value sum() const; AVLTree &map(const std::function &); int depth() const; void show() const; private: std::shared_ptr left, right; Key key; Value val; Bias bias; void show_all() const; bool sub_insert(const Key &, const Value &); void turn_right(); void turn_left(); void double_right(); void double_left(); bool increase_right(); bool increase_left(); void sub_map(const std::function &); }; AVLTree::AVLTree(const Key &k, const Value &v, const std::shared_ptr &l, const std::shared_ptr &r, const Bias &b) :key{ k }, val{ v }, left{ l }, right{ r }, bias{ b } {}; AVLTree::AVLTree() :key{}, val{}, left{ nullptr }, right{ nullptr }, bias{ Bias::Equal } {}; void AVLTree::incriment(const Key &k) { sub_insert(k, 1); } AVLTree::Value AVLTree::sum() const { Value res = val; if (left) res += left->sum(); if (right) res += right->sum(); return res; } AVLTree &AVLTree::map(const std::function &f) { sub_map(f); return *this; } int AVLTree::depth() const { int res = 1; if (left) res += left->depth(); if (right && right->depth() >= res) res = right->depth() + 1; return res; } void AVLTree::show() const { show_all(); std::cout << std::endl; } void AVLTree::show_all() const { std::cout << "-(" << key << "," << val << ")"; if (left) { left->show_all(); } if (right) { right->show_all(); } } bool AVLTree::sub_insert(const Key &k, const Value &v) { if (k == key) { val += v; return false; } else if (k < key) { if (!left || left->sub_insert(k, v)) { if (!left) left = std::make_shared(AVLTree(k, v)); return increase_left(); } else return false; } else { if (!right || right->sub_insert(k, v)) { if (!right) right = std::make_shared(AVLTree(k, v)); return increase_right(); } else return false; } } void AVLTree::turn_right() { const auto a = left->left; const auto b = left->right; const auto c = right; switch (left->bias) { case Bias::Equal: right = std::make_shared(AVLTree(key, val, b, c, Bias::Left)); bias = Bias::Right; break; case Bias::Left: right = std::make_shared(AVLTree(key, val, b, c, Bias::Equal)); bias = Bias::Equal; } key = left->key; val = left->val; left = a; } void AVLTree::turn_left() { const auto a = left; const auto b = right->left; const auto c = right->right; switch (right->bias) { case Bias::Equal: left = std::make_shared(AVLTree(key, val, a, b, Bias::Right)); bias = Bias::Left; break; case Bias::Right: left = std::make_shared(AVLTree(key, val, a, b, Bias::Equal)); bias = Bias::Equal; } key = right->key; val = right->val; right = c; } void AVLTree::double_right() { const auto a = left->left; const auto b = left->right->left; const auto c = left->right->right; const auto d = right; switch (left->right->bias) { case Bias::Equal: right = std::make_shared(AVLTree(key, val, c, d, Bias::Equal)); left->bias = Bias::Equal; break; case Bias::Right: right = std::make_shared(AVLTree(key, val, c, d, Bias::Equal)); left->bias = Bias::Left; break; case Bias::Left: right = std::make_shared(AVLTree(key, val, c, d, Bias::Right)); left->bias = Bias::Equal; } val = left->right->val; key = left->right->key; left->right = b; bias = Bias::Equal; } void AVLTree::double_left() { const auto a = left; const auto b = right->left->left; const auto c = right->left->right; const auto d = right->right; switch (right->left->bias) { case Bias::Equal: left = std::make_shared(AVLTree(key, val, a, b, Bias::Equal)); right->bias = Bias::Equal; break; case Bias::Left: left = std::make_shared(AVLTree(key, val, a, b, Bias::Equal)); right->bias = Bias::Right; break; case Bias::Right: left = std::make_shared(AVLTree(key, val, a, b, Bias::Left)); right->bias = Bias::Equal; } val = right->left->val; key = right->left->key; right->left = c; bias = Bias::Equal; } bool AVLTree::increase_right() { switch (bias) { case Bias::Equal: bias = Bias::Right; return true; break; case Bias::Left: bias = Bias::Equal; return false; break; case Bias::Right: switch (right->bias) { case Bias::Equal: turn_left(); return true; break; case Bias::Left: double_left(); return false; break; case Bias::Right: turn_left(); return false; } } } bool AVLTree::increase_left() { switch (bias) { case Bias::Equal: bias = Bias::Left; return true; break; case Bias::Right: bias = Bias::Equal; return false; break; case Bias::Left: switch (left->bias) { case Bias::Equal: turn_right(); return true; break; case Bias::Right: double_right(); return false; break; case Bias::Left: turn_right(); return false; } } } void AVLTree::sub_map(const std::function &f) { val = f(val); if (left) left->sub_map(f); if (right) right->sub_map(f); } int main() { int n; std::cin >> n; AVLTree tree; for (; n > 0; --n) { int v; std::cin >> v; tree.incriment(v); } std::cout << tree.map([](const int &n) {return (n == 1) ? 1 : 0; }).sum() << std::endl; return 0; }