题解：P9507 [BalkanOI2018] Popa

· · 题解

题意是构造一棵树，满足第 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;
}