题解

思路概述

• 交互库要求维护若干以中序序列为主体的二叉树，支持“拼接”“分裂”“访问”。实现上把每棵树视为一棵 Treap：节点随机权重（rnd）保证平衡，其中中序遍历正好对应序列顺序。
• join(x,y)：把两棵 Treap 依据随机权重合并，并记录合并过程中的操作（通过 move 接口通知评测环境更改结构）。最终得到的新根赋给编号 tot+1，并返回新树两个手下对应的旧结点编号。
• split(x,k)：把 Treap x 按中序第 k 个位置拆成两棵。通过递归调整随机权重并调用 move 修改儿子指针，实现“权重 Treap + 中序第 k 个节点”分割，返回新树手下所在的节点编号。
• visit(x)：访问时需要把树恢复为“合法的 Treap 形态”，代码会针对当前根不断旋转/调整子树，使得所有祖先都被重新连回 Treap，并返回根节点编号。

说明

• 树上维护的每个节点含左右儿子指针、父指针、子树大小等信息；为了让交互库同步结构，所有结构修改都体现为 move() 调用：移动工人到指定节点并调整儿子指针，同时浇水恢复节点状态。
• maxdep、maxcnt 限制靠随机权重 Treap 保证平衡，确保单次 join/split/visit 的 move 次数不超过限制。

复杂度

• Treap 操作期望 O(log n)；整套解法在交互库的限制下可以顺利运行。

#include"tree.h"
#include<bits/stdc++.h>
using namespace std;
namespace solution{

const int MAX_N=5e5;

class Node{

public:

    Node *c[2];

    Node *f;

    int sz;

    int id;

    int rnd;

    void pushUp(){

        this->sz=this->c[0]->sz+this->c[1]->sz+1;

    }

};

int n;

int tot;

Node t[MAX_N];

constexpr Node *null=&t[0];

Node *root[MAX_N],*g[MAX_N][2];

bool good[MAX_N];

void init(int N,int maxdep,int maxcnt){

    mt19937 rnd(time(0));

    n=N;

    tot=n;

    null->c[0]=null;

    null->c[1]=null;

    null->sz=0;

    null->id=0;

    for(int i=1;i<=n;++i){

        t[i].c[0]=null;

        t[i].c[1]=null;

        t[i].f=null;

        t[i].sz=1;

        t[i].id=i;

        t[i].rnd=rnd();

        root[i]=&t[i];

        g[i][0]=&t[i];

        g[i][1]=&t[i];

        good[i]=true;

    }

}

void changeChild(Node *p,int k,Node *q){

    p->c[k]->f=null;

    p->c[k]=q;

    q->f->c[q->f->c[1]==q]=null;

    q->f=p;

}

void join(int x,int y,int &id1,int &id2){

    Node *p=g[x][1];

    Node *q=g[y][0];

    while(p!=null&&q!=null){

        if(p->rnd>q->rnd){

            while(q->f!=null&&q->f->rnd<p->rnd){

                q->pushUp();

                q=q->f;

                move(y,1,q->id,-1,-1);

            }

            Node *f=q->f;

            if(f!=null){

                move(y,1,f->id,-1,-1);

            }

            move(x,2,p->id,1,q->id);

            changeChild(p,1,q);

            q->pushUp();

            q=f;

        }else{

            while(p->f!=null&&p->f->rnd<=q->rnd){

                p->pushUp();

                p=p->f;

                move(x,2,p->id,-1,-1);

            }

            Node *f=p->f;

            if(f!=null){

                move(x,2,f->id,-1,-1);

            }

            move(y,1,q->id,0,p->id);

            changeChild(q,0,p);

            p->pushUp();

            p=f;

        }

    }

    ++tot;

    while(p!=null){

        p->pushUp();

        root[tot]=p;

        p=p->f;

    }

    while(q!=null){

        q->pushUp();

        root[tot]=q;

        q=q->f;

    }

    good[tot]=false;

    g[tot][0]=g[x][0];

    g[tot][1]=g[y][1];

    id1=1;

    id2=4;

}

void split(int x,int k,int &p1,int &p2,int &p3,int &p4){

    Node *p;

    int id;

    if(k*2<=root[x]->sz){

        id=1;

        p=g[x][0];

        while(p->sz<k){

            p=p->f;

            move(x,1,p->id,-1,-1);

        }

        while(true){

            if(p->c[0]->sz>=k){

                p=p->c[0];

                move(x,1,p->id,-1,-1);

            }else if(k==p->c[0]->sz+1){

                break;

            }else{

                k-=p->c[0]->sz+1;

                p=p->c[1];

                move(x,1,p->id,-1,-1);

            }

        }

    }else{

        id=2;

        k=root[x]->sz-k+1;

        p=g[x][1];

        while(p->sz<k){

            p=p->f;

            move(x,2,p->id,-1,-1);

        }

        while(true){

            if(p->c[1]->sz>=k){

                p=p->c[1];

                move(x,2,p->id,-1,-1);

            }else if(k==p->c[1]->sz+1){

                break;

            }else{

                k-=p->c[1]->sz+1;

                p=p->c[0];

                move(x,2,p->id,-1,-1);

            }

        }

    }

    root[tot+1]=p;

    root[tot+2]=p->c[1];

    p1=g[x][0]->id;

    g[tot+1][0]=g[x][0];

    p2=p->id;

    g[tot+1][1]=p;

    p4=g[x][1]->id;

    g[tot+2][1]=g[x][1];

    if(p->c[1]!=null){

        move(x,id,p->id,1,0);

        changeChild(p,1,null);

    }

    p->pushUp();

    while(p->f!=null){

        if(p->f->c[1]==p){

            p=p->f;

            move(x,id,p->id,1,root[tot+1]->id);

            changeChild(p,1,root[tot+1]);

            root[tot+1]=p;

        }else{

            p=p->f;

            move(x,id,p->id,0,root[tot+2]->id);

            changeChild(p,0,root[tot+2]);

            root[tot+2]=p;

        }

        p->pushUp();

    }

    good[tot+1]=good[x];

    good[tot+2]=good[x];

    p=root[tot+2];

    while(p->c[0]!=null){

        p=p->c[0];

    }

    g[tot+2][0]=p;

    p3=p->id;

    tot+=2;

}

int visit(int x){

    if(!good[x]){

        stack<int> stk;

        for(Node *p=g[x][0];p->f!=null;p=p->f){

            move(x,1,p->f->id,-1,-1);

            stk.push(p->id);

        }

        while(!stk.empty()){

            move(x,1,stk.top(),-1,-1);

            stk.pop();

        }

        for(Node *p=g[x][1];p->f!=null;p=p->f){

            move(x,2,p->f->id,-1,-1);

            stk.push(p->id);

        }

        while(!stk.empty()){

            move(x,2,stk.top(),-1,-1);

            stk.pop();

        }

        good[x]=true;

    }

    return root[x]->id;

}

}

void init(int N,int maxdep,int maxcnt){

    solution::init(N,maxdep,maxcnt);

}

void join(int x,int y,int &id1,int &id2){

    solution::join(x,y,id1,id2);

}

void split(int x,int k,int &p1,int &p2,int &p3,int &p4){

    solution::split(x,k,p1,p2,p3,p4);

}

int visit(int x){

    return solution::visit(x);

}