#include #include #include class AVLTree { enum class Bias : char { Left, Right, Equal }; using Key = int; using Value = bool; public: AVLTree(const Key &, const Value & = Value{}, std::unique_ptr && = { nullptr }, std::unique_ptr && = { nullptr }, const Bias & = Bias::Equal); AVLTree(); void insert(const Key &, const Value &); Value &operator[](const Key &); bool has_key(const Key &) const; void erase(const Key &); private: Value val; std::unique_ptr left, right; Key key; Bias bias; bool initialized; 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(); bool reduce_right(); bool reduce_left(); const AVLTree* leften() const; bool erase_leften(); bool sub_erase(const Key &); bool is_not_leaf() const; }; AVLTree::AVLTree(const Key &k, const Value &v, std::unique_ptr &&l, std::unique_ptr &&r, const Bias &b) :key{ k }, val{ v }, left{ std::move(l) }, right{ std::move(r) }, bias{ b }, initialized{ true } {}; AVLTree::AVLTree() :key{}, val{}, left{ nullptr }, right{ nullptr }, bias{ Bias::Equal }, initialized{ false } {}; void AVLTree::insert(const Key &k, const Value &v) { if (initialized) sub_insert(k, v); else { key = k; val = v; initialized = true; } } AVLTree::Value &AVLTree::operator[](const Key &k) { if (k == key) { return val; } else if (k < key) { return left->operator[](k); } else { return right->operator[](k); } } bool AVLTree::has_key(const Key &k) const { if (k == key) return true; else if (k < key && left) return left->has_key(k); else if (k > key && right) return right->has_key(k); return false; } void AVLTree::erase(const Key &k) { if (initialized) { if (k == key) initialized = false; else sub_erase(k); } } bool AVLTree::sub_insert(const Key &k, const Value &v) { if (k < key) { if (!left || left->sub_insert(k, v)) { if (!left) left = std::unique_ptr(new AVLTree(k, v)); return increase_left(); } else return false; } else if (k > key) { if (!right || right->sub_insert(k, v)) { if (!right) right = std::unique_ptr(new AVLTree(k, v)); return increase_right(); } else return false; } return false; } void AVLTree::turn_right() { switch (left->bias) { case Bias::Equal: right = std::unique_ptr(new AVLTree(key, val, std::move(left->right), std::move(right), Bias::Left)); bias = Bias::Right; break; case Bias::Left: right = std::unique_ptr(new AVLTree(key, val, std::move(left->right), std::move(right), Bias::Equal)); bias = Bias::Equal; } key = left->key; val = left->val; left = std::move(left->left); } void AVLTree::turn_left() { switch (right->bias) { case Bias::Equal: left = std::unique_ptr(new AVLTree(key, val, std::move(left), std::move(right->left), Bias::Right)); bias = Bias::Left; break; case Bias::Right: left = std::unique_ptr(new AVLTree(key, val, std::move(left), std::move(right->left), Bias::Equal)); bias = Bias::Equal; } key = right->key; val = right->val; right = std::move(right->right); } void AVLTree::double_right() { left->turn_left(); turn_right(); } void AVLTree::double_left() { right->turn_right(); turn_left(); } 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; } } } bool AVLTree::reduce_right() { return !increase_left(); } bool AVLTree::reduce_left() { return !increase_right(); } const AVLTree* AVLTree::leften() const { if (left) return left->leften(); else return this; } bool AVLTree::erase_leften() { if (left->left) { if (left->erase_leften()) return reduce_left(); else return false; } else { left = std::move(left->right); return true; } } bool AVLTree::sub_erase(const Key &k) { if (k < key) { if (left->is_not_leaf()) { if (left->sub_erase(k)) return reduce_left(); else return false; } else { left.reset(); return bool(right); } } else if (k > key) { if (right->is_not_leaf()) { if (right->sub_erase(k)) return reduce_right(); else return false; } else { right.reset(); return bool(left); } } else { if (right) { auto l = right->leften(); val = l->val; key = l->key; if (right->erase_leften()) return reduce_right(); else return false; } else { *this = std::move(*left); return true; } } }; bool AVLTree::is_not_leaf() const { return right || left; } int main() { AVLTree root; int n; std::cin >> n; std::vector vector(n); for (auto &v:vector){ std::cin >> v; if (root.has_key(v)) root[v] = false; else root.insert(v, true); } int sum = 0; for (const auto &v:vector){ if (root[v]) ++sum; } std::cout << sum << std::endl; return 0; }