题目理解

这是 BalkanOI 2018 Popa 问题的解决方案。题目要求通过有限的GCD查询构建满足特定条件的二叉树。

代码思路解析

1. 核心观察

题目有两个关键条件：

1. 中序遍历有序：节点编号 0,1,...,N-1 就是中序遍历顺序
2. 整除关系：父节点的S值整除子节点的S值

2. 单调栈建树

F(i, 0, n - 1) {
    while (top && query(stk[top], i, i, i))
        top--;
    fa[i] = stk[top];
    stk[++top] = i;
}

这里使用了单调栈技巧：

• query(stk[top], i, i, i) 检查 gcd(stk[top]...i) 是否等于 gcd(i)
• 如果相等，说明 S[stk[top]] 整除 S[i]，可以弹出栈顶
• 最终 fa[i] 记录每个节点的父节点

3. 递归构建二叉树

function<i64(i64, i64)> cdq = [&](i64 l, i64 r)->i64{
    if (l > r) return -1;
    
    vector<i64> V;
    i64 now = r;
    while (now >= l)
        V.push_back(now), now = fa[now];
    
    reverse(V.begin(), V.end());
    // 构建左右子树
};

通过CDQ分治思想：

• 从右往左收集节点形成链
• 链上的节点构成父子关系
• 递归处理链节点之间的区间作为左子树

4. 树结构赋值

F(i, 0, (i64)V.size() - 1) {
    Left[V[i]] = cdq(lst, V[i] - 1);  // 左子树
    Right[V[i]] = (i + 1 == V.size() ? -1 : V[i + 1]);  // 右子节点
    lst = V[i] + 1;
}

关键技巧

1. 单调栈应用

利用GCD查询构建近似的"笛卡尔树"结构

2. 查询优化

query(stk[top], i, i, i)

这个查询检查 gcd(stk[top]...i) == gcd(i)，即 S[i] 是否能被栈顶整除

3. 链分解

通过父指针链将区间分解为可递归处理的子问题

4. 中序遍历保持

算法天然保持节点编号的中序顺序

复杂度分析

查询复杂度：

• 每个节点最多入栈出栈一次
• 每次出栈需要一次查询
• 总查询次数：O(n)

时间复杂度：

• 单调栈：O(n)
• 递归构建：O(n)
• 总复杂度：O(n)

正确性证明

整除关系：

通过 query(stk[top], i, i, i) 确保父节点整除子节点

中序遍历：

节点按编号顺序处理，递归划分保持中序性质

树结构：

通过链分解和递归构建确保形成合法的二叉树

总结

这个解法巧妙地将问题转化为单调栈+分治问题：

1. 问题转化：利用GCD查询检测整除关系
2. 单调栈：高效构建近似的父子关系
3. 分治构建：递归构造满足条件的二叉树
4. 查询优化：用最少的查询完成构建

体现了竞赛中交互题和构造题的典型解题思路，特别是利用单调性优化查询次数的技巧很有启发性。