OI-wiki（信奥知识百科）项目源代码

#include <bits/stdc++.h> #define CPPIO \ std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0); #define freep(p) p ? delete p, p = nullptr, void(1) : void(0) #if defined(BACKLIGHT) && !defined(NASSERT) #define ASSERT(x) \ ((x) || (fprintf(stderr, "assertion failed (" __FILE__ ":%d): \"%s\"\n", \ __LINE__, #x), \ assert(false), false)) #else #define ASSERT(x) ; #endif #ifdef BACKLIGHT #include "debug.h" #else #define logd(...) ; #endif using i64 = int64_t; using u64 = uint64_t; void solve_case(int Case); int main(int argc, char* argv[]) { CPPIO; int T = 1; // std::cin >> T; for (int t = 1; t <= T; ++t) { solve_case(t); } return 0; } /** * Dynamic Forest Maintained With Euler Tour Tree. * * As said in reference, link and cut operation of dynamic trees can be * transformed into sequence split and sequence merge operation, which can be * easily maintained using balanced search trees like Treap. * * @reference: Dynamic trees as search trees via euler tours, applied to the * network simplex algorithm by Robert E. Tarjan. * https://link.springer.com/article/10.1007/BF02614369 */ class DynamicForest { private: static std::mt19937 rng_; struct Node { int size_; int priority_; Node* left_; Node* right_; Node* parent_; int from_; int to_; int num_vertex_; int num_edge_; Node(int from, int to) : size_(1), priority_(rng_()), left_(nullptr), right_(nullptr), parent_(nullptr), from_(from), to_(to), num_vertex_(from_ == to_ ? 1 : 0), num_edge_(from_ == to_ ? 0 : 1) {} void Maintain() { size_ = 1; num_vertex_ = from_ == to_ ? 1 : 0; num_edge_ = from_ == to_ ? 0 : 1; if (left_) { size_ += left_->size_; left_->parent_ = this; num_vertex_ += left_->num_vertex_; num_edge_ += left_->num_edge_; } if (right_) { size_ += right_->size_; right_->parent_ = this; num_vertex_ += right_->num_vertex_; num_edge_ += right_->num_edge_; } } }; static int GetSize(Node* p) { return p == nullptr ? 0 : p->size_; } static Node* FindRoot(Node* p) { if (!p) return nullptr; while (p->parent_ != nullptr) p = p->parent_; return p; } static std::string to_string(Node* p) { std::stringstream ss; ss << "Node [\n"; std::function<void(Node*)> dfs = [&](Node* p) { if (!p) return; dfs(p->left_); ss << "(" << p->from_ << "," << p->to_ << "),"; dfs(p->right_); }; dfs(p); ss << "]\n\n"; return ss.str(); } Node* AllocateNode(int u, int v) { Node* p = new Node(u, v); return p; } void FreeNode(Node*& p) { if (p) { delete p; p = nullptr; } } /* * Dynamic Sequence Maintained using Treap. */ class Treap { public: /** * Merge two treap a and b into a single treap, with keys in a less than * keys in b. * * In the other word, concating sequence a and sequence b. */ static Node* Merge(Node* a, Node* b) { if (a == nullptr) return b; if (b == nullptr) return a; if (a->priority_ < b->priority_) { a->right_ = Merge(a->right_, b); a->Maintain(); return a; } else { b->left_ = Merge(a, b->left_); b->Maintain(); return b; } } /** * Get the number of nodes with keys less than or equal to the key of p. * * In the other word, the the 1-based index of p inside the sequencec * containing p. */ static int GetPosition(Node* p) { ASSERT(p != nullptr); int position = GetSize(p->left_) + 1; while (p) { if (p->parent_ && p == p->parent_->right_) position += GetSize(p->parent_->left_) + 1; p = p->parent_; } return position; } /** * Split sequence containning p into two sequences, the first one contains * the first k elements, the second one contains the remaining elements. */ static std::pair<Node*, Node*> Split(Node* p, int k) { if (!p) return {nullptr, nullptr}; std::pair<Node*, Node*> result; if (GetSize(p->left_) < k) { auto right_result = Split(p->right_, k - GetSize(p->left_) - 1); p->right_ = right_result.first; result.first = p; result.second = right_result.second; } else { auto left_result = Split(p->left_, k); p->left_ = left_result.second; result.first = left_result.first; result.second = p; } p->Maintain(); if (result.first) result.first->parent_ = nullptr; if (result.second) result.second->parent_ = nullptr; return result; } /* * Bottom up split treap p into 2 treaps a and b. * - a: a treap containing nodes with position less than or equal to p. * - b: a treap containing nodes with postion greater than p. * * In the other word, split sequence containning p into two sequences, the * first one contains elements before p and element p, the second one * contains elements after p. */ static std::pair<Node*, Node*> SplitUp2(Node* p) { ASSERT(p != nullptr); Node *a = nullptr, *b = nullptr; b = p->right_; if (b) b->parent_ = nullptr; p->right_ = nullptr; bool is_p_left_child_of_parent = false; bool is_from_left_child = false; while (p) { Node* parent = p->parent_; if (parent) { is_p_left_child_of_parent = (parent->left_ == p); if (is_p_left_child_of_parent) { parent->left_ = nullptr; } else { parent->right_ = nullptr; } p->parent_ = nullptr; } if (!is_from_left_child) { a = Merge(p, a); } else { b = Merge(b, p); } is_from_left_child = is_p_left_child_of_parent; p->Maintain(); p = parent; } return {a, b}; } /* * Bottom up split treap p into 3 treaps a, b and c. * - a: a treap containing nodes with key less than p. * - b: a treap containing nodes with key greater than p. * - c: a treap containing nodes with key equal p. * * In the other word, split sequence containning p into three sequences, the * first one contains elements before p, the second one contains element p, * the third one contains elements after p. */ static std::tuple<Node*, Node*, Node*> SplitUp3(Node* p) { ASSERT(p != nullptr); Node* a = p->left_; if (a) a->parent_ = nullptr; p->left_ = nullptr; Node* b = p->right_; if (b) b->parent_ = nullptr; p->right_ = nullptr; Node* c = p; bool is_p_left_child_of_parent = false; bool is_from_left_child = false; Node* parent = p->parent_; if (parent) { is_p_left_child_of_parent = (parent->left_ == p); if (is_p_left_child_of_parent) { parent->left_ = nullptr; } else { parent->right_ = nullptr; } p->parent_ = nullptr; } is_from_left_child = is_p_left_child_of_parent; p->Maintain(); p = parent; while (p) { Node* parent = p->parent_; if (parent) { is_p_left_child_of_parent = (parent->left_ == p); if (is_p_left_child_of_parent) { parent->left_ = nullptr; } else { parent->right_ = nullptr; } p->parent_ = nullptr; } if (!is_from_left_child) { a = Merge(p, a); } else { b = Merge(b, p); } is_from_left_child = is_p_left_child_of_parent; p->Maintain();