#include #include #include template class AVLTree { enum class Bias :char { L = 'L', Eq = 'E', R = 'R' }; struct Tree { V val; Tree *left{ nullptr }, *right{ nullptr }; K key; Bias bias{ Bias::Eq }; Tree(const K &, const V &); ~Tree(); bool has_key(const K &) const; V &operator[](const K &); Tree* find_leften() const; int depth() const; void show() const; }; public: AVLTree(); ~AVLTree(); void insert(const K &, const V &); void erase(const K &); bool has_key(const K &) const; size_t size() const; int depth() const; void show_all() const; V &operator[](const K &); private: int factor_size{ 0 }; Tree* tree{ nullptr }; bool single_right(Tree* &top); bool single_left(Tree* &top); void turn_right(Tree* &top); void turn_left(Tree* &top); bool double_right(Tree* &top); bool double_left(Tree* &top); bool insert_by_key(const K &, const V &, Tree* &); bool increase_right(Tree* &); bool increase_left(Tree* &); bool reduce_right(Tree* &); bool reduce_left(Tree* &); bool erase_by_key(const K &, Tree* &); bool void_leften(Tree* &); void move_position(Tree* &from, Tree* &to); }; template int AVLTree::depth() const { if (factor_size == 0) return 0; else return tree->depth(); } template int AVLTree::Tree::depth() const { if (left && right) { switch (bias) { case Bias::Eq: case Bias::R: return right->depth() + 1; case Bias::L: return left->depth() + 1; } } else { if (bias == Bias::Eq) return 1; else return 2; } } template void AVLTree::show_all() const { if (factor_size == 0) std::cout << "null\n"; else tree->show(); } template void AVLTree::Tree::show() const { std::cout << '[' << key << ',' << val << "] "; if (left) left->show(); if (right) right->show(); } template AVLTree::AVLTree() {}; template AVLTree::~AVLTree() { delete tree; }; template void AVLTree::insert(const K &k, const V &v) { if (factor_size++ > 0) insert_by_key(k, v, tree); else tree = new Tree(k, v); } template void AVLTree::erase(const K &k) { assert(factor_size > 0 && tree->has_key(k)); erase_by_key(k, tree); --factor_size; } template bool AVLTree::has_key(const K &k) const { return factor_size > 0 && tree->has_key(k); } template V &AVLTree::operator[](const K &k) { assert(factor_size > 0 && tree->has_key(k)); return tree->operator[](k); } template size_t AVLTree::size() const { return factor_size; } template AVLTree::Tree::Tree(const K &k, const V &v) :key{ k }, val{ v } {}; template AVLTree::Tree::~Tree() { delete left; delete right; } template bool AVLTree::Tree::has_key(const K &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); else return false; } template V &AVLTree::Tree::operator[](const K &k) { if (k == key) return val; else if (k < key && left) return left->operator[](k); else if (k > key && right) return right->operator[](k); else assert(false); } template typename AVLTree::Tree* AVLTree::Tree::find_leften() const { if (left) return left->find_leften(); else return this; } template void AVLTree::turn_right(Tree* &top) { auto const old_left = top->left; top->left = top->left->right; old_left->right = top; top = old_left; }; template void AVLTree::turn_left(Tree* &top) { auto const old_right = top->right; top->right = top->right->left; old_right->left = top; top = old_right; }; template bool AVLTree::single_right(Tree *&top) { turn_right(top); switch (top->bias) { case Bias::L: top->bias = Bias::Eq; top->right->bias = Bias::Eq; return false; case Bias::Eq: top->bias = Bias::R; top->right->bias = Bias::L; return true; default: assert(false); } } template bool AVLTree::single_left(Tree *&top) { turn_left(top); switch (top->bias) { case Bias::R: top->bias = Bias::Eq; top->left->bias = Bias::Eq; return false; case Bias::Eq: top->bias = Bias::L; top->left->bias = Bias::R; return true; default: assert(false); } } template bool AVLTree::double_right(Tree* &top) { turn_left(top->left); turn_right(top); switch (top->bias) { case Bias::Eq: top->bias = Bias::Eq; top->left->bias = Bias::Eq; top->right->bias = Bias::Eq; return false; case Bias::R: top->bias = Bias::Eq; top->left->bias = Bias::L; top->right->bias = Bias::Eq; return false; case Bias::L: top->bias = Bias::Eq; top->left->bias = Bias::Eq; top->right->bias = Bias::R; return false; default: assert(false); } }; template bool AVLTree::double_left(Tree* &top) { turn_right(top->right); turn_left(top); switch (top->bias) { case Bias::Eq: top->bias = Bias::Eq; top->left->bias = Bias::Eq; top->right->bias = Bias::Eq; return false; case Bias::L: top->bias = Bias::Eq; top->left->bias = Bias::Eq; top->right->bias = Bias::R; return false; case Bias::R: top->bias = Bias::Eq; top->left->bias = Bias::L; top->right->bias = Bias::Eq; return false; default: assert(false); } }; template bool AVLTree::insert_by_key(const K &k, const V &v, Tree* &top) { assert(top->key != k); if (k < (top->key)) { if (!top->left || insert_by_key(k, v, top->left)) { if (!top->left) top->left = new Tree(k, v); return increase_left(top); } else return false; } else { if (!top->right || insert_by_key(k, v, top->right)) { if (!top->right) top->right = new Tree(k, v); return increase_right(top); } else return false; } } template bool AVLTree::increase_right(Tree* &top) { switch (top->bias) { case Bias::R: switch (top->right->bias) { case Bias::L: return double_left(top); default: return single_left(top); } case Bias::Eq: top->bias = Bias::R; return true; case Bias::L: top->bias = Bias::Eq; return false; default: assert(false); } } template bool AVLTree::increase_left(Tree* &top) { switch (top->bias) { case Bias::L: switch (top->left->bias) { case Bias::R: return double_right(top); default: return single_right(top); } case Bias::Eq: top->bias = Bias::L; return true; case Bias::R: top->bias = Bias::Eq; return false; default: assert(false); } } template bool AVLTree::reduce_right(Tree* &top) { return !increase_left(top); } template bool AVLTree::reduce_left(Tree* &top) { return !increase_right(top); } template bool AVLTree::erase_by_key(const K &k, Tree* &top) { if (k == top->key) { if (top->right) { auto leften = top->right->find_leften(); auto flag = void_leften(top->right); assert(!leften->left); move_position(leften, top); if (flag) return reduce_right(top); else return false; } else { if (top->left) move_position(top->left, top); else { delete top; top = nullptr; } return true; } } else if (k < top->key) { assert(top->left); if (erase_by_key(k, top->left)) return reduce_left(top); else return false; } else { assert(top->right); if (erase_by_key(k, top->right)) return reduce_right(top); else return false; } } template bool AVLTree::void_leften(Tree* &top) { if (top->left) { if (void_leften(top->left)) return reduce_left(top); else return false; } else { if (top->right) top = top->right; else top = nullptr; return true; } } template void AVLTree::move_position(Tree* &from, Tree* &to) { from->left = to->left; from->right = to->right; from->bias = to->bias; auto temp = to; to = from; temp->left = nullptr; temp->right = nullptr; delete temp; } int main() { int n; std::cin >> n; std::vector vector(n); AVLTree tree; for (auto &v : vector) { std::cin >> v; if (tree.has_key(v)) tree[v] = false; else tree.insert(v, true); } int sum = 0; for (const auto &v : vector) { if (tree[v]) ++sum; } std::cout << sum << std::endl; return 0; }