自动搬运

查看原文

来自洛谷，原作者为

	晴空一鹤 恰似人间惊鸿客，墨染星辰云水间

搬运于2025-08-24 22:49:01，当前版本为作者最后更新于2024-06-24 16:27:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意是构造一棵树，满足第 $i$ 号节点权值为 $S_i$，且树的节点标号的中序遍历为 $1,2,...,n$，且树上每个儿子的权值都是他父亲的倍数，保证有解。你不知道 $S$ 数组的具体情况，但你可以询问一段 $S_i$ 的 $\gcd$ 是否等于另一段 $S_i$ 的 $\gcd$。

初看非常神秘，于是使用加点法观察。

假设我们已经对于前 $i$ 个节点构造了一棵符合条件的树，现在我们要加入节点 $i+1$。

考虑中序遍历的条件，我们发现这个点只能要么放在当前根的父亲（把根作为该节点的左儿子），要么挂在根节点开始的连续右链上（把下一个节点扳成左儿子），其他地方这个点都不会成为最后一个被遍历的。

我们维护右链，从链底向根依次尝试挂上去，由于每次挂点最多使右链长度加一，每一次尝试失败就会使右链长度减一，那我们总的尝试的规模大概为 $2n$ 次，刚好符合限制。

把尝试对应到询问上，我们要了解该点权值与链上节点是否有倍数关系，设处理到的链上节点为 $x$，那么这等价于 $\gcd(S_x,S_{i+1})=S_x=\gcd(S_x,S_x)$，用 $query$ 函数查即可。

有的读者可能会说，$query$ 只能查连续区间的 $\gcd$ 吧，但众所周知倍数具有传递关系，且中序遍历这一限制使得 $x+1$ 到 $i$ 这一堆节点都是 $x$ 节点直接或间接的子结点，所以这一段的 $\gcd$ 就等于 $S_x$ 和 $S_{i+1}$ 的 $\gcd$。

要注意的……哦，首先这题询问次数限制很严格，因此我们直接只判第二种情况，因为保证有解，第二种失败了那第一种不用查询肯定成功。

还有注意本题节点下标从 0 开始。

solve 部分代码

int solve(int N, int* Left, int* Right) {
    int l[1005],r[1005],g=1,op[3005],cnt=0,ma=0;
    for(int i=1;i<=2*N;i++)op[i]=0;
    for(int i=1;i<=N;i++)
    l[i]=r[i]=-1;
    for(int i=2;i<=N;i++){
      op[0]=g;ma=0;
      for(int j=cnt;j>=0;j--)if(query(op[j]-1,i-1,op[j]-1,op[j]-1))
      {l[i]=r[op[j]];r[op[j]]=i-1;cnt=j+1;op[cnt]=i;ma=1;break;}
      if(!ma){l[i]=g-1;g=i;cnt=0;}    
     }
    for(int i=1;i<=N;i++)Left[i-1]=l[i],Right[i-1]=r[i];
    return g-1;
}