#731366 (C++17) No.1787 Do Use Dynamic Tree

提出ソース
結果

問題	No.1787 Do Use Dynamic Tree
ユーザー	👑 Nachia
提出日時	2022-01-16 06:47:59
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3,186 ms / 10,000 ms
コード長	29,551 bytes
コンパイル時間	1,184 ms
コンパイル使用メモリ	87,716 KB
実行使用メモリ	56,408 KB
最終ジャッジ日時	2024-11-22 20:10:35
合計ジャッジ時間	49,890 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	1 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	9 ms 5,248 KB
testcase_13	AC	9 ms 5,248 KB
testcase_14	AC	12 ms 5,248 KB
testcase_15	AC	9 ms 5,248 KB
testcase_16	AC	10 ms 5,248 KB
testcase_17	AC	10 ms 5,248 KB
testcase_18	AC	10 ms 5,248 KB
testcase_19	AC	8 ms 5,248 KB
testcase_20	AC	7 ms 5,248 KB
testcase_21	AC	11 ms 5,248 KB
testcase_22	AC	2,280 ms 33,152 KB
testcase_23	AC	1,806 ms 46,464 KB
testcase_24	AC	1,983 ms 28,800 KB
testcase_25	AC	3,186 ms 49,664 KB
testcase_26	AC	2,932 ms 49,664 KB
testcase_27	AC	2,840 ms 49,692 KB
testcase_28	AC	1,922 ms 56,320 KB
testcase_29	AC	2,345 ms 56,268 KB
testcase_30	AC	2,301 ms 56,320 KB
testcase_31	AC	2,328 ms 56,380 KB
testcase_32	AC	2,667 ms 56,304 KB
testcase_33	AC	2,945 ms 56,208 KB
testcase_34	AC	1,449 ms 56,388 KB
testcase_35	AC	2,267 ms 56,408 KB
testcase_36	AC	3,060 ms 56,012 KB
testcase_37	AC	2,372 ms 48,384 KB
testcase_38	AC	2,599 ms 48,384 KB
testcase_39	AC	2,572 ms 48,512 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code

#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* right_child = nullptr;
    TopTreeNode* left_child = nullptr;
    TopTreeNode* mid_child = nullptr;
    UnderlyingTreeVertex* boundary_left = nullptr;
    UnderlyingTreeVertex* boundary_right = 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(){
        if(left_child) left_child->parent = nullptr;
        if(right_child) right_child->parent = nullptr;
        if(mid_child) mid_child->parent = nullptr;
    }
    void unblock(TopTreeNode* new_root){
        if (left_child && !left_child->is_root()) left_child = new_root;
        if (right_child && !right_child->is_root()) right_child = new_root;
        if (mid_child && !mid_child->is_root()) mid_child = new_root;
        if(node_type == NODE_TYPE_COMPRESS){
            bottomup_compress(left_child, mid_child, right_child);
        }
        if(node_type == NODE_TYPE_RAKE){
            bottomup_rake(left_child, right_child);
        }
    }

    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;
    left_child = nullptr;
    right_child = nullptr;
    mid_child = nullptr;
    boundary_left = nullptr;
    boundary_right = nullptr;
    bouundary_vertices_are_reversed = false;
}

TopTreeNode*& TopTreeNode::parentchild(){
    TopTreeNode* p = parent;
    if(p->left_child == this) return p->left_child;
    if(p->right_child == this) return p->right_child;
    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_left, boundary_right);
    data.reverse();
    if(node_type == NODE_TYPE_COMPRESS){
        std::swap(left_child, right_child);
    }
}

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){
            left_child->reverse_boundary_vertices();
            right_child->reverse_boundary_vertices();
        }
    }
    bouundary_vertices_are_reversed = false;

    auto f = lazy_data;
    if(node_type == NODE_TYPE_COMPRESS){
        left_child->apply_lazy_data(f);
        if(mid_child){
            mid_child->apply_lazy_data(f);
            mid_child->boundary_left->data = TopTreeClusterEffect::mapping_vertex(f, mid_child->boundary_left->data);
        }
        right_child->apply_lazy_data(f);
        left_child->boundary_right->data = TopTreeClusterEffect::mapping_vertex(f, left_child->boundary_right->data);
    }
    if(node_type == NODE_TYPE_RAKE){
        left_child->apply_lazy_data(f);
        right_child->apply_lazy_data(f);
        right_child->boundary_left->data = TopTreeClusterEffect::mapping_vertex(f, right_child->boundary_left->data);
    }
    lazy_data = TopTreeClusterEffect::id();
}
void TopTreeNode::bottomup_update(){
    if(node_type == NODE_TYPE_COMPRESS){
        auto cent = left_child->boundary_right;
        auto l_data = left_child->data;
        auto r_data = right_child->data;
        if (mid_child) {
            l_data = TopTreeClusterData::rake(l_data, mid_child->data, mid_child->boundary_left->data);
        }
        data = TopTreeClusterData::compress(l_data, cent->data, r_data);
    }
    else if(node_type == NODE_TYPE_RAKE){
        data = TopTreeClusterData::rake(left_child->data, right_child->data, right_child->boundary_left->data);
    }
}

void TopTreeNode::bottomup_edge(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r){
    node_type = NODE_TYPE_EDGE;
    left_child = nullptr;
    right_child = nullptr;
    mid_child = nullptr;
    boundary_left = l;
    boundary_right = 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_left->handle = l;
    if(r->node_type != NODE_TYPE_RAKE) r->boundary_left->handle = r;
    if (!special_for_hard_expose) {
        node_type = NODE_TYPE_RAKE;
        boundary_left = l->boundary_left;
        boundary_right = l->boundary_right;
        left_child = l;
        l->parent = this;
        mid_child = nullptr;
        right_child = r;
        r->parent = this;
        bottomup_update();
    }
    else {
        node_type = NODE_TYPE_RAKE;
        boundary_left = l->boundary_left;
        boundary_right = l->boundary_right;
        left_child = l;
        l->parent = this;
        mid_child = nullptr;
        right_child = r;
        r->parent = this;
        auto buf = left_child->data;
        buf.reverse();
        buf = TopTreeClusterData::rake(buf, right_child->data, right_child->boundary_left->data);
        buf.reverse();
        data = buf;
    }
}
void TopTreeNode::bottomup_compress(TopTreeNode* l, TopTreeNode* m_rake, TopTreeNode* r){
    UnderlyingTreeVertex* bound = l->boundary_right;
    node_type = NODE_TYPE_COMPRESS;
    boundary_left = l->boundary_left;
    boundary_right = r->boundary_right;
    left_child = l;
    l->parent = this;
    mid_child = m_rake;
    if(m_rake) m_rake->parent = this;
    right_child = r;
    r->parent = this;

    if(mid_child && mid_child->node_type != NODE_TYPE_RAKE) mid_child->boundary_left->handle = mid_child;

    boundary_left->handle = this;
    bound->handle = this;
    boundary_right->handle = this;
    bottomup_update();
}

void TopTreeNode::rotate_rake_left(){
    auto p = parent;
    
    if(!p->is_root()) p->parentchild() = this;
    parent = p->parent;

    auto c0 = p->left_child;
    auto c1 = left_child;
    auto c2 = right_child;
    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 = left_child;
    auto c1 = right_child;
    auto c2 = p->right_child;
    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->left_child;
    auto c4 = this->left_child;
    auto c6 = this->right_child;
    p->bottomup_compress(c1, p_rake, c4);
    bottomup_compress(p, c_rake, c6);
}
void TopTreeNode::rotate_compress_right(){
    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 = this->left_child;
    auto c3 = this->right_child;
    auto c6 = p->right_child;
    p->bottomup_compress(c3, p_rake, c6);
    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->left_child == this){ rotate_rake_right(); }
            else{ rotate_rake_left(); }
        }
        else{
            auto pp = p->parent;
            if(p->left_child == this){
                if(pp->left_child == p){ p->rotate_rake_right(); rotate_rake_right(); }
                else { rotate_rake_right(); rotate_rake_left(); }
            }
            else{
                if(pp->right_child == 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->left_child == this){ rotate_compress_right(); }
            else{ rotate_compress_left(); }
        }
        else{
            auto pp = p->parent;
            if(p->left_child == this){
                if(pp->left_child == p){ p->rotate_compress_right(); rotate_compress_right(); }
                else { rotate_compress_right(); rotate_compress_left(); }
            }
            else{
                if(pp->right_child == 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->left_child == this);
    while(p->node_type == NODE_TYPE_RAKE){
        if(is_this_left_child){
            rake_r = p->right_child;
            rake_rp = p;
        }
        else{
            rake_l = p->left_child;
            rake_lp = p;
        }
        auto pp = p->parent;
        is_this_left_child = (pp->left_child == p);
        p = pp;
    }

    if(compress_on_left){
        auto rake_r1 = p->left_child;
        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->right_child);
    }
    else{
        reverse_boundary_vertices();
        auto rake_r1 = p->right_child;
        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->left_child, rake_r1, this);
    }
}
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_left == r || n_r->boundary_right == l){
            n_r->reverse_boundary_vertices();
        }
        n_r->lazy_propagation();
    }
    else{
        l->exposing_source(r);
        n_r = r->handle;
        if(n_r->right_child == 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_left == target) n_target->reverse_boundary_vertices();
    if(n_target->boundary_right == target){
        exposing_target();
        return true;
    }
    
    handle->get_propagated();

    // block
    n_target->left_child->parent = nullptr;
    n_target->right_child->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;
    }

    if (!n_target->left_child->is_root()) n_target->left_child = c;
    if (!n_target->right_child->is_root()) n_target->right_child = 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->right_child == p->parent) compress_to_left = false;
        c->splice(compress_to_left);
        c = c->parent;
        if(n_target == c){
            n_target->left_child->parent = nullptr;
            n_target->right_child->parent = nullptr;
        }
    }

    c = handle;
    c->get_propagated();
    c->splay_compress();
    if (!n_target->left_child->is_root()) n_target->left_child = c;
    if (!n_target->right_child->is_root()) n_target->right_child = c;
    n_target->bottomup_compress(n_target->left_child, n_target->mid_child, n_target->right_child);
    if(c->is_root()) return false;

    if(n_target->right_child == c){
        n_target->reverse_boundary_vertices();
        n_target->lazy_propagation();
    }
    return true;
}


TopTree::HardExposeUndoUnit::HardExposeUndoUnit(TopTreeNode* v){
    to = v;
    l = v->left_child;
    m_rake = v->mid_child;
    r = v->right_child;
}
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);
}

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;
    if(l->handle->boundary_left != l) r = l->handle->boundary_left;
    if(l->handle->boundary_right != l) r = l->handle->boundary_right;

    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->right_child->reverse_boundary_vertices();
            TopTreeNode* rake_r = c->right_child;
            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->left_child, 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->left_child;
            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->right_child, 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_left == l && n_r->boundary_right == r){
            // case (3) (4)
            // do nothing
        }
        else if(n_r->boundary_left == l){
            // case (1)
            hard_expose_rake_case1(n_r);
        }
        else if(n_r->boundary_right == 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->left_child->node_type == TopTreeNode::NODE_TYPE_RAKE){
                    most_left_rake = most_left_rake->left_child;
                    most_left_rake->lazy_propagation();
                }
                most_left_rake->splay_soft_rake();
                most_left_rake = most_left_rake->left_child;
                most_left_rake->reverse_boundary_vertices();
                c->bottomup_compress(c->left_child, c->mid_child->right_child, most_left_rake);
            }
            else{
                // case (2)
                c->mid_child->reverse_boundary_vertices();
                c->bottomup_compress(c->left_child, nullptr, c->mid_child);
            }
        }
        else{
            // case (1)
            auto cc = c->left_child;
            cc->parent = nullptr;
            delete(c);
            c = cc;
            c->boundary_left->handle = c;
            c->boundary_right->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_left == l && n_r->boundary_right == r){
        // case (3)
        return false;
    }
    if(n_r->boundary_left == l){
        // case (1)
        n_r->reverse_boundary_vertices();
        std::swap(l, r);
        // reduce to case (2)
    }
    if(n_r->boundary_right == r){
        // case (2)
        n_r->lazy_propagation();
        auto lr = n_r->right_child;
        if(lr->node_type != TopTreeNode::NODE_TYPE_EDGE) return false;
        delete(lr);
        n_r->right_child = 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->right_child;
    if(lr->node_type != TopTreeNode::NODE_TYPE_EDGE) return false;
    delete(lr);
    n_r->left_child = nullptr;
    n_l->right_child = nullptr;
    n_l->parent = nullptr;
    fix_tmporary_state(n_l);
    n_r->left_child = n_r->right_child;
    n_r->left_child->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_left == c){
            n_c->reverse_boundary_vertices();
        }
        if(n_c->boundary_right == c){
            // c is a leaf
            auto unstable_root = new TopTreeNode();
            n_c->parent = unstable_root;
            unstable_root->left_child = n_c;
            return unstable_root;
        }
        // c is not a leaf
        n_c->lazy_propagation();
        auto r_rake = n_c->right_child;
        n_c->right_child = 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->left_child, n_l->mid_child, lr);
        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->left_child, n_r->right_child);
    n_r->right_child->reverse_boundary_vertices();
    auto lr = new TopTreeNode();
    lr->bottomup_edge(l, r);
    n_r->bottomup_compress(lr, n_r->mid_child, n_r->right_child);
    n_l->bottomup_compress(n_l->left_child, n_l->mid_child, n_r);
    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;
}
yukicoder

結果

テストケース

ソースコード
