P9507 [BalkanOI 2018] Popa

翻译自 BalkanOI 2018 Day2 T2「Popa」 > *"He's an outlaw and he's famous* > *Andrii Popa the courageous.* > *Day and night he rides,* > *He takes his tribute from the main road* > *And everywhere in the country* > *The thief catchers are running away as fast as they can"* > > *\- ["Andrii Popa", Phoenix](https://music.163.com/song?id=508736536)*

Ghiță 有一个下标从 $0$ 开始的正整数序列 $S$。因为他是喀尔巴阡的国王，所以他想要构造一个节点编号为 $0,1,\ldots ,N-1$ 的二叉树，满足： - 树的中序遍历按节点编号升序排列。二叉树的中序遍历由以根的左子节点（如果存在）为根形成的子树的中序遍历，根的节点编号和以根的右子节点（如果存在）为根形成的子树的中序遍历顺次连接组成。 - 如果 $x$ 是 $y$ 节点的父亲，那么 $S_x$ 整除 $S_y$。 二叉树是一种树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。 不幸的是，著名的亡命之徒 Andrii Popa 偷走了序列 $S$，Ghiță 不能直接获取到。但对于任意两个连续的子序列 $[a,b]$ 和 $[c,d]$，他可以使用最先进的技术（他的手机）求出 $\gcd[a,b]$ 是否等于 $\gcd [c,d]$，其中 $\gcd[x,y]$ 指 $S_x,S_{x+1},S_{x+2},\ldots ,S_y$ 的最大公因数。不幸的是，这项技术十分昂贵——如果 Ghiță 使用超过 $Q$ 次，他将会支付一大笔罚金。请帮他在使用这项技术最多 $Q$ 次的情况下构建出他想要的树。保证这是可能的。任何合法的构建方案都可以被接受。 ### 交互 本题只支持 C++ 语言使用函数交互。选手代码并不需要也不能包含 `popa.h`。 选手需实现如下函数： ```cpp int solve(int N, int* Left, int* Right); ``` 函数需返回树的根节点，并且将 `Left[i]` 和 `Right[i]` 分别赋值为 $i$ 的左子节点和右子节点。如果节点 $i$ 没有左子节点，则 `Left[i]` 应被赋为 $-1$，如果节点 $i$ 没有右子节点，则 `Right[i]` 应被赋为 $-1$。`Left` 和 `Right` 分别指向两个空间已被分配好且长度恰好为 $N$ 的数组。 函数 `solve` 在一次运行中会被调用最多 $5$ 次。我们建议谨慎使用全局变量。 选手可以调用如下函数（注意，选手须在代码中声明此函数）： ```cpp int query(int a, int b, int c, int d); ``` 这个函数当且仅当 $\gcd[a,b]=\gcd[c,d]$ 时返回 $1$，其中 $0\le a\le b

见「交互」。

见「交互」。

### 数据范围 | 子任务编号 | 限制 | 分值 | | :----------: | :----------: | :----------: | | $1$ | $N=100,Q=10^4$ | $37$ | | $2$ | $N=10^3,Q=2\times 10^4$ | $24$ | | $3$ | $N=10^3,Q=2\times 10^3$ | $39$ |