結果
問題 | No.1787 Do Use Dynamic Tree |
ユーザー | 👑 Nachia |
提出日時 | 2022-09-17 01:03:26 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,822 ms / 10,000 ms |
コード長 | 28,993 bytes |
コンパイル時間 | 924 ms |
コンパイル使用メモリ | 87,560 KB |
実行使用メモリ | 56,448 KB |
最終ジャッジ日時 | 2024-12-21 23:55:07 |
合計ジャッジ時間 | 41,441 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 8 ms
5,248 KB |
testcase_13 | AC | 8 ms
5,248 KB |
testcase_14 | AC | 10 ms
5,248 KB |
testcase_15 | AC | 8 ms
5,248 KB |
testcase_16 | AC | 9 ms
5,248 KB |
testcase_17 | AC | 10 ms
5,248 KB |
testcase_18 | AC | 8 ms
5,248 KB |
testcase_19 | AC | 8 ms
5,248 KB |
testcase_20 | AC | 7 ms
5,248 KB |
testcase_21 | AC | 10 ms
5,248 KB |
testcase_22 | AC | 1,971 ms
33,152 KB |
testcase_23 | AC | 1,607 ms
46,268 KB |
testcase_24 | AC | 1,601 ms
28,800 KB |
testcase_25 | AC | 2,605 ms
49,684 KB |
testcase_26 | AC | 2,561 ms
49,656 KB |
testcase_27 | AC | 2,603 ms
49,752 KB |
testcase_28 | AC | 1,668 ms
56,448 KB |
testcase_29 | AC | 1,635 ms
56,320 KB |
testcase_30 | AC | 1,679 ms
56,448 KB |
testcase_31 | AC | 2,234 ms
56,320 KB |
testcase_32 | AC | 2,541 ms
56,368 KB |
testcase_33 | AC | 2,822 ms
56,064 KB |
testcase_34 | AC | 1,354 ms
56,320 KB |
testcase_35 | AC | 2,147 ms
56,420 KB |
testcase_36 | AC | 2,728 ms
56,072 KB |
testcase_37 | AC | 2,084 ms
48,512 KB |
testcase_38 | AC | 2,039 ms
48,384 KB |
testcase_39 | AC | 2,012 ms
48,400 KB |
ソースコード
#include <vector> #include <utility> #include <algorithm> #include <cassert> #include <string> #include <iostream> struct TopTreeVertexData{ int x; int index; static TopTreeVertexData e(){ return { -1, -1 }; } }; struct TopTreeClusterData{ int raked[2] = {-1,-1}; int rake_ans[2] = {-1,-1}; int ans[2] = {-1,-1}; int nx_rake[2] = {-1,-1}; int nx_rake_ans[2] = {-1,-1}; int nx[2] = {-1,-1}; static TopTreeClusterData e(){ return TopTreeClusterData(); } static TopTreeClusterData compress(TopTreeClusterData l, TopTreeVertexData mid, TopTreeClusterData r){ int mid_rake = std::max(l.raked[1], r.raked[0]); int mid_rake_ans = (mid_rake == l.raked[1]) ? l.rake_ans[1] : r.rake_ans[0]; TopTreeClusterData res; for(int t=0; t<2; t++){ res.raked[t] = l.raked[t]; res.rake_ans[t] = l.rake_ans[t]; if(l.ans[t] != -1) res.ans[t] = l.ans[t]; else if(mid.x < l.nx_rake[t^1]) res.ans[t] = l.nx_rake_ans[t^1]; else if(r.nx[t] == -1) res.ans[t] = -1; else if(r.nx[t] < mid_rake) res.ans[t] = mid_rake_ans; else res.ans[t] = r.ans[t]; if(l.nx[t] == -1){ res.nx_rake[t] = mid_rake; res.nx_rake_ans[t] = mid_rake_ans; res.nx[t] = mid.x; } else{ res.nx_rake[t] = l.nx_rake[t]; res.nx_rake_ans[t] = l.nx_rake_ans[t]; res.nx[t] = l.nx[t]; } std::swap(l,r); } return res; } int query(TopTreeVertexData tg){ int nx_ex = (nx[1] == -1) ? tg.x : nx[1]; if(nx_ex < raked[1]) return rake_ans[1]; if(ans[1] != -1) return ans[1]; if(tg.x < nx_rake[0]) return nx_rake_ans[0]; if(raked[0] == -1) return tg.index; return rake_ans[0]; } static TopTreeClusterData rake(TopTreeClusterData l, TopTreeClusterData r, TopTreeVertexData r_end){ int mid_rake = std::max({ l.raked[1], r.raked[1], r.nx[1] }); int mid_rake_ans = -1; if(mid_rake == r.raked[1]) mid_rake_ans = r.rake_ans[1]; else if(mid_rake == r.nx[1]){ if(r.ans[1] != -1) mid_rake_ans = r.ans[1]; else if(r_end.x < r.nx_rake[0]) mid_rake_ans = r.nx_rake_ans[0]; else if(r.raked[0] == -1) mid_rake_ans = r_end.index; else mid_rake_ans = r.rake_ans[0]; } else if(mid_rake == l.raked[1]) mid_rake_ans = l.rake_ans[1]; if(r.nx[1] == -1 && mid_rake < r_end.x){ mid_rake = r_end.x; mid_rake_ans = r_end.index; } TopTreeClusterData res; res.raked[0] = l.raked[0]; res.rake_ans[0] = l.rake_ans[0]; res.raked[1] = mid_rake; res.rake_ans[1] = mid_rake_ans; res.ans[0] = l.ans[0]; res.ans[1] = l.ans[1]; res.nx_rake[0] = l.nx_rake[0]; res.nx_rake_ans[0] = l.nx_rake_ans[0]; res.nx_rake[1] = l.nx_rake[1]; res.nx_rake_ans[1] = l.nx_rake_ans[1]; res.nx[0] = l.nx[0]; res.nx[1] = l.nx[1]; return res; } void reverse(){ std::swap(raked[0], raked[1]); std::swap(rake_ans[0], rake_ans[1]); std::swap(ans[0], ans[1]); std::swap(nx_rake[0], nx_rake[1]); std::swap(nx_rake_ans[0], nx_rake_ans[1]); std::swap(nx[0], nx[1]); } }; struct TopTreeClusterEffect{ static TopTreeClusterEffect id(){ return {}; } static TopTreeClusterData mapping_cluster(TopTreeClusterEffect f, TopTreeClusterData x){ return x; } static TopTreeVertexData mapping_vertex(TopTreeClusterEffect f, TopTreeVertexData x){ return x; } static TopTreeClusterEffect composition(TopTreeClusterEffect l, TopTreeClusterEffect r){ return {}; } }; struct TopTreeNode; struct UnderlyingTreeVertex; struct TopTree; struct TopTreeNode{ public: TopTreeNode* parent = nullptr; TopTreeNode* child[2] = { nullptr, nullptr }; TopTreeNode* mid_child = nullptr; UnderlyingTreeVertex* boundary[2] = { nullptr, nullptr }; bool bouundary_vertices_are_reversed = false; enum TopTreeNodeType { NODE_TYPE_DISABLED, NODE_TYPE_EDGE, NODE_TYPE_RAKE, NODE_TYPE_COMPRESS }; TopTreeNodeType node_type = NODE_TYPE_DISABLED; TopTreeClusterData data = TopTreeClusterData::e(); TopTreeClusterEffect lazy_data = TopTreeClusterEffect::id(); void get_propagated(); private: void disable(); TopTreeNode*& parentchild(); public: void block(){ for(int t : {0,1}) if(child[t]) child[t]->parent = nullptr; if(mid_child) mid_child->parent = nullptr; } void unblock(TopTreeNode* new_root){ for(int t : {0,1}) if (child[t] && !child[t]->is_root()) child[t] = new_root; if(mid_child && !mid_child->is_root()) mid_child = new_root; if(node_type == NODE_TYPE_COMPRESS){ bottomup_compress(child[0], mid_child, child[1]); bottomup_update(); } if(node_type == NODE_TYPE_RAKE){ bottomup_rake(child[0], child[1]); } } void reverse_boundary_vertices(); void apply_lazy_data(TopTreeClusterEffect f); void lazy_propagation(); void bottomup_update(); void bottomup_edge(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r); void bottomup_rake(TopTreeNode* l, TopTreeNode* r, bool special_for_hard_expose = false); void bottomup_compress(TopTreeNode* l, TopTreeNode* m_rake, TopTreeNode* r); void rotate_rake_left(); void rotate_rake_right(); void rotate_compress_left(); void rotate_compress_right(); void splay_soft_rake(); void splay_rake(); void splay_compress(); void splice(bool hard_expose_rake_to_left = true); bool is_enabled() const { return node_type != NODE_TYPE_DISABLED; } bool is_rake_root() const { return !parent || parent->node_type != NODE_TYPE_RAKE; } bool is_compress_root() const { if(!parent) return true; if(parent->node_type != NODE_TYPE_COMPRESS) return true; return parent->mid_child == this; } bool is_root() const { return !parent; } }; struct UnderlyingTreeVertex{ TopTreeNode* handle; TopTreeVertexData data; UnderlyingTreeVertex(){ handle = nullptr; data = TopTreeVertexData::e(); } void exposing_target(bool e = false); bool exposing_source(UnderlyingTreeVertex* target); }; struct TopTree{ private: void soft_expose(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r); void undo_hard_expose(); public: TopTreeNode* expose(UnderlyingTreeVertex* l); TopTreeNode* expose(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r, bool do_hard = true); bool cut(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r); bool link(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r); struct HardExposeUndoUnit{ TopTreeNode* to = nullptr; TopTreeNode* l = nullptr; bool l_reversed = false; TopTreeNode* m_rake = nullptr; bool m_rake_reversed = false; TopTreeNode* r = nullptr; bool r_reversed = false; HardExposeUndoUnit(){} HardExposeUndoUnit(TopTreeNode*); void execute(); }; int hard_expose_undo_length = 0; HardExposeUndoUnit hard_expose_undo_memo[2]; int hard_expose_new_rakes_length = 0; std::pair<TopTreeNode*, bool> hard_expose_new_rakes[10] = {}; }; void TopTreeNode::disable(){ node_type = NODE_TYPE_DISABLED; parent = nullptr; child[0] = nullptr; child[1] = nullptr; mid_child = nullptr; boundary[0] = nullptr; boundary[1] = nullptr; bouundary_vertices_are_reversed = false; } TopTreeNode*& TopTreeNode::parentchild(){ TopTreeNode* p = parent; for(int t : {0,1}) if(p->child[t] == this) return p->child[t]; if(p->mid_child == this) return p->mid_child; exit(1); } void TopTreeNode::reverse_boundary_vertices(){ bouundary_vertices_are_reversed = !bouundary_vertices_are_reversed; std::swap(boundary[0], boundary[1]); data.reverse(); if(node_type == NODE_TYPE_COMPRESS){ std::swap(child[0], child[1]); } } void TopTreeNode::get_propagated(){ TopTreeNode* pp = parent; TopTreeNode* p = this; TopTreeNode* tmp = nullptr; p->parent = nullptr; while(pp){ tmp = pp->parent; pp->parent = p; p = pp; pp = tmp; } while(p){ p->lazy_propagation(); tmp = p->parent; p->parent = pp; pp = p; p = tmp; } } void TopTreeNode::apply_lazy_data(TopTreeClusterEffect f){ lazy_data = TopTreeClusterEffect::composition(f, lazy_data); data = TopTreeClusterEffect::mapping_cluster(f, data); } void TopTreeNode::lazy_propagation(){ if(bouundary_vertices_are_reversed){ if(node_type == NODE_TYPE_COMPRESS){ for(int t : {0,1}) child[t]->reverse_boundary_vertices(); } } bouundary_vertices_are_reversed = false; auto f = lazy_data; if(node_type == NODE_TYPE_COMPRESS){ for(int t : {0,1}) child[t]->apply_lazy_data(f); if(mid_child){ mid_child->apply_lazy_data(f); mid_child->boundary[0]->data = TopTreeClusterEffect::mapping_vertex(f, mid_child->boundary[0]->data); } child[0]->boundary[1]->data = TopTreeClusterEffect::mapping_vertex(f, child[0]->boundary[1]->data); } if(node_type == NODE_TYPE_RAKE){ for(int t : {0,1}) child[t]->apply_lazy_data(f); child[1]->boundary[0]->data = TopTreeClusterEffect::mapping_vertex(f, child[1]->boundary[0]->data); } lazy_data = TopTreeClusterEffect::id(); } void TopTreeNode::bottomup_update(){ if(node_type == NODE_TYPE_COMPRESS){ auto cent = child[0]->boundary[1]; auto l_data = child[0]->data; auto r_data = child[1]->data; if (mid_child) { l_data = TopTreeClusterData::rake(l_data, mid_child->data, mid_child->boundary[0]->data); } data = TopTreeClusterData::compress(l_data, cent->data, r_data); } else if(node_type == NODE_TYPE_RAKE){ data = TopTreeClusterData::rake(child[0]->data, child[1]->data, child[1]->boundary[0]->data); } } void TopTreeNode::bottomup_edge(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r){ node_type = NODE_TYPE_EDGE; child[0] = nullptr; child[1] = nullptr; mid_child = nullptr; boundary[0] = l; boundary[1] = r; l->handle = this; r->handle = this; data = TopTreeClusterData::e(); lazy_data = TopTreeClusterEffect::id(); } void TopTreeNode::bottomup_rake(TopTreeNode* l, TopTreeNode* r, bool special_for_hard_expose){ if(l->node_type != NODE_TYPE_RAKE) l->boundary[0]->handle = l; if(r->node_type != NODE_TYPE_RAKE) r->boundary[0]->handle = r; if (!special_for_hard_expose) { node_type = NODE_TYPE_RAKE; for(int t : {0,1}) boundary[t] = l->boundary[t]; child[0] = l; l->parent = this; mid_child = nullptr; child[1] = r; r->parent = this; bottomup_update(); } else { node_type = NODE_TYPE_RAKE; for(int t : {0,1}) boundary[t] = l->boundary[t]; child[0] = l; l->parent = this; mid_child = nullptr; child[1] = r; r->parent = this; auto buf = child[0]->data; buf.reverse(); buf = TopTreeClusterData::rake(buf, child[1]->data, child[1]->boundary[0]->data); buf.reverse(); data = buf; } } void TopTreeNode::bottomup_compress(TopTreeNode* l, TopTreeNode* m_rake, TopTreeNode* r){ UnderlyingTreeVertex* bound = l->boundary[1]; node_type = NODE_TYPE_COMPRESS; boundary[0] = l->boundary[0]; boundary[1] = r->boundary[1]; child[0] = l; l->parent = this; mid_child = m_rake; if(m_rake) m_rake->parent = this; child[1] = r; r->parent = this; if(mid_child && mid_child->node_type != NODE_TYPE_RAKE) mid_child->boundary[0]->handle = mid_child; bound->handle = this; for(int t : {0,1}) boundary[t]->handle = this; } void TopTreeNode::rotate_rake_left(){ auto p = parent; if(!p->is_root()) p->parentchild() = this; parent = p->parent; auto c0 = p->child[0]; auto c1 = child[0]; auto c2 = child[1]; p->bottomup_rake(c0, c1); bottomup_rake(p, c2); } void TopTreeNode::rotate_rake_right(){ auto p = parent; if(!p->is_root()) p->parentchild() = this; parent = p->parent; auto c0 = child[0]; auto c1 = child[1]; auto c2 = p->child[1]; p->bottomup_rake(c1, c2); bottomup_rake(c0, p); } void TopTreeNode::rotate_compress_left(){ auto p = parent; if(!p->is_root()) p->parentchild() = this; parent = p->parent; auto p_rake = p->mid_child; auto c_rake = this->mid_child; auto c1 = p->child[0]; auto c4 = this->child[0]; auto c6 = this->child[1]; p->bottomup_compress(c1, p_rake, c4); p->bottomup_update(); bottomup_compress(p, c_rake, c6); } void TopTreeNode::rotate_compress_right(){ auto p = parent; std::swap(p->data, data); if(!p->is_root()) p->parentchild() = this; parent = p->parent; auto p_rake = p->mid_child; auto c_rake = this->mid_child; auto c1 = this->child[0]; auto c3 = this->child[1]; auto c6 = p->child[1]; p->bottomup_compress(c3, p_rake, c6); p->bottomup_update(); bottomup_compress(c1, c_rake, p); } void TopTreeNode::splay_soft_rake(){ while(!is_rake_root()){ auto p = parent; if(p->is_rake_root()){ if(p->child[0] == this){ rotate_rake_right(); } else{ rotate_rake_left(); } } else{ auto pp = p->parent; if(p->child[0] == this){ if(pp->child[0] == p){ p->rotate_rake_right(); rotate_rake_right(); } else { rotate_rake_right(); rotate_rake_left(); } } else{ if(pp->child[1] == p){ p->rotate_rake_left(); rotate_rake_left(); } else { rotate_rake_left(); rotate_rake_right(); } } } } } void TopTreeNode::splay_rake(){ if(is_rake_root()) return; auto p1 = parent; p1->splay_soft_rake(); auto p2 = parent; if(p2 == p1) return; p1->block(); p2->splay_soft_rake(); p1->unblock(p2); } void TopTreeNode::splay_compress(){ while(!is_compress_root()){ auto p = parent; if(p->is_compress_root()){ if(p->child[0] == this){ rotate_compress_right(); } else{ rotate_compress_left(); } } else{ auto pp = p->parent; if(p->child[0] == this){ if(pp->child[0] == p){ p->rotate_compress_right(); rotate_compress_right(); } else { rotate_compress_right(); rotate_compress_left(); } } else{ if(pp->child[1] == p){ p->rotate_compress_left(); rotate_compress_left(); } else { rotate_compress_left(); rotate_compress_right(); } } } } } void TopTreeNode::splice(bool compress_on_left){ TopTreeNode* p = nullptr; TopTreeNode* rake_l = nullptr; TopTreeNode* rake_lp = nullptr; TopTreeNode* rake_r = nullptr; TopTreeNode* rake_rp = nullptr; p = parent; bool is_this_left_child = (p->child[0] == this); while(p->node_type == NODE_TYPE_RAKE){ if(is_this_left_child){ rake_r = p->child[1]; rake_rp = p; } else{ rake_l = p->child[0]; rake_lp = p; } auto pp = p->parent; is_this_left_child = (pp->child[0] == p); p = pp; } if(compress_on_left){ auto rake_r1 = p->child[0]; if(rake_l){ rake_lp->bottomup_rake(rake_l, rake_r1); rake_r1 = rake_lp; } if(rake_r){ rake_rp->bottomup_rake(rake_r1, rake_r); rake_r1 = rake_rp; } p->bottomup_compress(this, rake_r1, p->child[1]); p->bottomup_update(); } else{ reverse_boundary_vertices(); auto rake_r1 = p->child[1]; rake_r1->reverse_boundary_vertices(); if(rake_l){ rake_lp->bottomup_rake(rake_l, rake_r1); rake_r1 = rake_lp; } if(rake_r){ rake_rp->bottomup_rake(rake_r1, rake_r); rake_r1 = rake_rp; } p->bottomup_compress(p->child[0], rake_r1, this); p->bottomup_update(); } } void TopTree::soft_expose(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r){ r->exposing_target(true); auto n_l = l->handle; auto n_r = r->handle; if(n_l == n_r){ if(n_r->boundary[0] == r || n_r->boundary[1] == l){ n_r->reverse_boundary_vertices(); } n_r->lazy_propagation(); } else{ l->exposing_source(r); n_r = r->handle; if(n_r->child[1] == n_l) n_r->reverse_boundary_vertices(); n_r->lazy_propagation(); n_l->lazy_propagation(); } } void UnderlyingTreeVertex::exposing_target(bool e){ TopTreeNode* n_this = handle; handle->get_propagated(); auto c = n_this; while(!c->is_root()){ if(!c->is_compress_root()){ c->splay_compress(); continue; } if(!c->is_rake_root()){ c->splay_rake(); while(!c->is_rake_root()) c = c->parent; continue; } c = c->parent; } c = n_this = handle; c->get_propagated(); while(!c->is_root()){ c->splice(); c = c->parent; } handle->splay_compress(); } bool UnderlyingTreeVertex::exposing_source(UnderlyingTreeVertex* target){ auto n_this = handle; auto n_target = target->handle; if(n_this == n_target) return true; if(n_target->node_type == TopTreeNode::NODE_TYPE_EDGE) return false; if(n_this->is_root()) return false; if(n_target->boundary[0] == target) n_target->reverse_boundary_vertices(); if(n_target->boundary[1] == target){ exposing_target(); return true; } handle->get_propagated(); // block for(int t : {0,1}) n_target->child[t]->parent = nullptr; auto c = n_this; while(!c->is_root()){ if(!c->is_compress_root()){ c->splay_compress(); continue; } if(!c->is_rake_root()){ c->splay_rake(); while(!c->is_rake_root()) c = c->parent; continue; } c = c->parent; } for(int t : {0,1}) if (!n_target->child[t]->is_root()) n_target->child[t] = c; c = n_this = handle; while(!c->is_root()){ auto p = c; while(!p->is_rake_root()) p = p->parent; bool compress_to_left = true; if(n_target->child[1] == p->parent) compress_to_left = false; c->splice(compress_to_left); c = c->parent; if(n_target == c){ for(int t : {0,1}) n_target->child[t]->parent = nullptr; } } c = handle; c->get_propagated(); c->splay_compress(); for(int t : {0,1}) if (!n_target->child[t]->is_root()) n_target->child[t] = c; n_target->bottomup_compress(n_target->child[0], n_target->mid_child, n_target->child[1]); n_target->bottomup_update(); if(c->is_root()) return false; if(n_target->child[1] == c){ n_target->reverse_boundary_vertices(); n_target->lazy_propagation(); } return true; } TopTree::HardExposeUndoUnit::HardExposeUndoUnit(TopTreeNode* v){ to = v; l = v->child[0]; m_rake = v->mid_child; r = v->child[1]; } void TopTree::HardExposeUndoUnit::execute(){ if (l_reversed) l->reverse_boundary_vertices(); if (m_rake_reversed) m_rake->reverse_boundary_vertices(); if (r_reversed) r->reverse_boundary_vertices(); to->bottomup_compress(l, m_rake, r); to->bottomup_update(); } void TopTree::undo_hard_expose(){ for(int i=hard_expose_new_rakes_length-1; i>=0; i--){ hard_expose_new_rakes[i].first->lazy_propagation(); } for(int i=hard_expose_new_rakes_length-1; i>=0; i--){ if(hard_expose_new_rakes[i].second) delete(hard_expose_new_rakes[i].first); } hard_expose_new_rakes_length = 0; for(int i=0; i<hard_expose_undo_length; i++){ hard_expose_undo_memo[i].execute(); } hard_expose_undo_length = 0; } TopTreeNode* TopTree::expose(UnderlyingTreeVertex* l){ undo_hard_expose(); if(!l->handle) return nullptr; UnderlyingTreeVertex* r = nullptr; for(int t : {0,1}) if(l->handle->boundary[t] != l) r = l->handle->boundary[t]; return expose(l, r); } TopTreeNode* TopTree::expose(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r, bool do_hard){ undo_hard_expose(); // soft expose soft_expose(l, r); auto n_l = l->handle; auto n_r = r->handle; // hard expose if(do_hard){ auto hard_expose_rake_case1 = [this](TopTreeNode* c)->void { hard_expose_undo_memo[hard_expose_undo_length++] = HardExposeUndoUnit(c); hard_expose_undo_memo[hard_expose_undo_length - 1].r_reversed = true; c->child[1]->reverse_boundary_vertices(); TopTreeNode* rake_r = c->child[1]; if(c->mid_child){ auto tmp = new TopTreeNode(); tmp->bottomup_rake(c->mid_child, rake_r); rake_r = tmp; hard_expose_new_rakes[hard_expose_new_rakes_length++] = std::make_pair(rake_r, true); } c->bottomup_rake(c->child[0], rake_r, false); hard_expose_new_rakes[hard_expose_new_rakes_length++] = std::make_pair(c, false); }; auto hard_expose_rake_case2 = [this](TopTreeNode* c)->void { hard_expose_undo_memo[hard_expose_undo_length++] = HardExposeUndoUnit(c); TopTreeNode* rake_r = c->child[0]; if(c->mid_child){ auto tmp = new TopTreeNode(); tmp->bottomup_rake(rake_r, c->mid_child); rake_r = tmp; hard_expose_new_rakes[hard_expose_new_rakes_length++] = std::make_pair(rake_r, true); } c->bottomup_rake(c->child[1], rake_r, true); hard_expose_new_rakes[hard_expose_new_rakes_length++] = std::make_pair(c, false); }; n_r->lazy_propagation(); n_l->lazy_propagation(); if(n_r->boundary[0] == l && n_r->boundary[1] == r){ // case (3) (4) // do nothing } else if(n_r->boundary[0] == l){ // case (1) hard_expose_rake_case1(n_r); } else if(n_r->boundary[1] == r){ // case (2) hard_expose_rake_case2(n_r); } else{ // case (5) hard_expose_rake_case2(n_l); hard_expose_rake_case1(n_r); } } return n_r; } bool TopTree::cut(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r){ if(!l){ std::cerr << "TopTree::link : l is null" << std::endl; exit(1); } if(!r){ std::cerr << "TopTree::link : r is null" << std::endl; exit(1); } undo_hard_expose(); auto fix_tmporary_state = [this](TopTreeNode* c)->TopTreeNode*{ if(c->mid_child){ if(c->mid_child->node_type == TopTreeNode::NODE_TYPE_RAKE){ // case (3) auto most_left_rake = c->mid_child; most_left_rake->lazy_propagation(); while(most_left_rake->child[0]->node_type == TopTreeNode::NODE_TYPE_RAKE){ most_left_rake = most_left_rake->child[0]; most_left_rake->lazy_propagation(); } most_left_rake->splay_soft_rake(); most_left_rake = most_left_rake->child[0]; most_left_rake->reverse_boundary_vertices(); c->bottomup_compress(c->child[0], c->mid_child->child[1], most_left_rake); c->bottomup_update(); } else{ // case (2) c->mid_child->reverse_boundary_vertices(); c->bottomup_compress(c->child[0], nullptr, c->mid_child); c->bottomup_update(); } } else{ // case (1) auto cc = c->child[0]; cc->parent = nullptr; delete(c); c = cc; c->boundary[0]->handle = c; c->boundary[1]->handle = c; } return c; }; soft_expose(l, r); auto n_l = l->handle; auto n_r = r->handle; if(n_r->node_type == TopTreeNode::NODE_TYPE_EDGE){ // case (4) l->handle = r->handle = nullptr; delete(n_l); return true; } if(n_r->boundary[0] == l && n_r->boundary[1] == r){ // case (3) return false; } if(n_r->boundary[0] == l){ // case (1) n_r->reverse_boundary_vertices(); std::swap(l, r); // reduce to case (2) } if(n_r->boundary[1] == r){ // case (2) n_r->lazy_propagation(); auto lr = n_r->child[1]; if(lr->node_type != TopTreeNode::NODE_TYPE_EDGE) return false; delete(lr); n_r->child[1] = nullptr; fix_tmporary_state(n_r); r->handle = nullptr; return true; } // case (5) n_r->lazy_propagation(); n_l->lazy_propagation(); auto lr = n_l->child[1]; if(lr->node_type != TopTreeNode::NODE_TYPE_EDGE) return false; delete(lr); n_r->child[0] = nullptr; n_l->child[1] = nullptr; n_l->parent = nullptr; fix_tmporary_state(n_l); n_r->child[0] = n_r->child[1]; n_r->child[0]->reverse_boundary_vertices(); fix_tmporary_state(n_r); return true; } bool TopTree::link(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r){ if(!l){ std::cerr << "TopTree::link : l is null" << std::endl; exit(1); } if(!r){ std::cerr << "TopTree::link : r is null" << std::endl; exit(1); } undo_hard_expose(); auto make_temporary_state = [this](UnderlyingTreeVertex* c)->TopTreeNode* { if(!c){ std::cerr << "TopTree::link internal error 1" << std::endl; exit(1); } if(!c->handle->is_root()){ std::cerr << "TopTree::link internal error 2 : not exposed" << std::endl; exit(1); } auto n_c = c->handle; if(n_c->boundary[0] == c){ n_c->reverse_boundary_vertices(); } if(n_c->boundary[1] == c){ // c is a leaf auto unstable_root = new TopTreeNode(); n_c->parent = unstable_root; unstable_root->child[0] = n_c; return unstable_root; } // c is not a leaf n_c->lazy_propagation(); auto r_rake = n_c->child[1]; n_c->child[1] = nullptr; r_rake->reverse_boundary_vertices(); if(n_c->mid_child){ auto rake_root = new TopTreeNode(); rake_root->bottomup_rake(n_c->mid_child, r_rake); r_rake = rake_root; } n_c->mid_child = r_rake; r_rake->parent = n_c; n_c->node_type = TopTreeNode::NODE_TYPE_DISABLED; return n_c; }; if(!l->handle) std::swap(l, r); if(!l->handle){ // cut case (4) TopTreeNode* c = new TopTreeNode(); c->bottomup_edge(l, r); return true; } if(!r->handle){ // r->handle == nullptr : cut case (2) l->exposing_target(); auto n_l = make_temporary_state(l); auto lr = new TopTreeNode(); lr->bottomup_edge(l, r); n_l->bottomup_compress(n_l->child[0], n_l->mid_child, lr); n_l->bottomup_update(); return true; } // cut case (5) l->exposing_target(); r->exposing_target(); if(l->handle == r->handle) return false; if(!l->handle->is_root()) return false; auto n_l = make_temporary_state(l); auto n_r = make_temporary_state(r); std::swap(n_r->child[0], n_r->child[1]); n_r->child[1]->reverse_boundary_vertices(); auto lr = new TopTreeNode(); lr->bottomup_edge(l, r); n_r->bottomup_compress(lr, n_r->mid_child, n_r->child[1]); n_r->bottomup_update(); n_l->bottomup_compress(n_l->child[0], n_l->mid_child, n_r); n_l->bottomup_update(); return true; } using namespace std; int main() { int N; cin >> N; vector<UnderlyingTreeVertex> A(N); for(int i=0; i<N; i++){ A[i].data.x = i; A[i].data.index = i; } TopTree top_tree; for(int i=0; i<N-1; i++){ int u,v; cin >> u >> v; u--; v--; top_tree.link(&A[u], &A[v]); } int Q; cin >> Q; int preans = 0; for(int i=0; i<Q; i++){ int u,v; cin >> u >> v; u--; v--; u = (u + preans) % N; v = (v + preans) % N; auto c = top_tree.expose(&A[v], &A[u]); swap(A[u].data.x, A[v].data.x); int ans = c->data.query(A[v].data); cout << (ans + 1) << "\n"; preans = ans + 1; } return 0; }