{"problem":{"name":"[BalkanOI 2018] Popa","description":{"content":"Ghiță 有一个下标从 $0$ 开始的正整数序列 $S$。因为他是喀尔巴阡的国王，所以他想要构造一个节点编号为 $0,1,\\ldots ,N-1$ 的二叉树，满足： - 树的中序遍历按节点编号升序排列。二叉树的中序遍历由以根的左子节点（如果存在）为根形成的子树的中序遍历，根的节点编号和以根的右子节点（如果存在）为根形成的子树的中序遍历顺次连接组成。   - 如果 $x$ 是 $y$ 节点的父亲","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":256000},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9507"},"statements":[{"statement_type":"Markdown","content":"Ghiță 有一个下标从 $0$ 开始的正整数序列 $S$。因为他是喀尔巴阡的国王，所以他想要构造一个节点编号为 $0,1,\\ldots ,N-1$ 的二叉树，满足：\n\n- 树的中序遍历按节点编号升序排列。二叉树的中序遍历由以根的左子节点（如果存在）为根形成的子树的中序遍历，根的节点编号和以根的右子节点（如果存在）为根形成的子树的中序遍历顺次连接组成。  \n- 如果 $x$ 是 $y$ 节点的父亲，那么 $S_x$ 整除 $S_y$。\n\n二叉树是一种树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。\n\n不幸的是，著名的亡命之徒 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$ 次的情况下构建出他想要的树。保证这是可能的。任何合法的构建方案都可以被接受。\n\n### 交互\n\n本题只支持 C++ 语言使用函数交互。选手代码并不需要也不能包含 `popa.h`。\n\n选手需实现如下函数：\n\n```cpp\nint solve(int N, int* Left, int* Right);\n```\n\n函数需返回树的根节点，并且将 `Left[i]` 和 `Right[i]` 分别赋值为 $i$ 的左子节点和右子节点。如果节点 $i$ 没有左子节点，则 `Left[i]` 应被赋为 $-1$，如果节点 $i$ 没有右子节点，则 `Right[i]` 应被赋为 $-1$。`Left` 和 `Right` 分别指向两个空间已被分配好且长度恰好为 $N$ 的数组。\n\n函数 `solve` 在一次运行中会被调用最多 $5$ 次。我们建议谨慎使用全局变量。\n\n选手可以调用如下函数（注意，选手须在代码中声明此函数）：\n\n```cpp\nint query(int a, int b, int c, int d);\n```\n\n这个函数当且仅当 $\\gcd[a,b]=\\gcd[c,d]$ 时返回 $1$，其中 $0\\le a\\le b<n,0\\le c\\le d<N$，否则返回 $0$。\n\n### 样例\n\n例如 $S=[12, 4, 16, 2, 2, 20]$，一组交互过程如下：\n\n| 调用 `solve` | 调用 `query` | 调用 `solve` 之后 |\n| :-----------: | :-----------: | :-----------: |\n| `solve(6, Left, Right)` |  |  |\n|  | `query(0, 1, 3, 5)` 返回 $0$ |  |\n|  | `query(4, 5, 1, 3)` 返回 $1$ |  |\n|  |  | `solve` 返回值为 $3$；`Left` 指向 $[-1, 0, -1, 1, -1, -1]$；`Right` 指向 $[-1, 2, -1, 4, 5, -1]$ |\n\n样例中，Ghiță 国王想要的树形态如下图所示。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/y5whph6a.png)\n\n## Input\n\n见「交互」。\n\n## Output\n\n见「交互」。\n\n[samples]\n\n## Background\n\n翻译自 BalkanOI 2018 Day2 T2「Popa」\n\n> *\"He's an outlaw and he's famous*  \n> *Andrii Popa the courageous.*  \n> *Day and night he rides,*  \n> *He takes his tribute from the main road*  \n> *And everywhere in the country*  \n> *The thief catchers are running away as fast as they can\"*\n> \n> *\\- [\"Andrii Popa\", Phoenix](https://music.163.com/song?id=508736536)*\n\n## Note\n\n### 数据范围\n\n| 子任务编号 | 限制 | 分值 |\n| :----------: | :----------: | :----------: |\n| $1$ | $N=100,Q=10^4$ | $37$ |\n| $2$ | $N=10^3,Q=2\\times 10^4$ | $24$ |\n| $3$ | $N=10^3,Q=2\\times 10^3$ | $39$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9507","tags":["2018","交互题","Special Judge","栈","构造","BalkanOI（巴尔干半岛）"],"sample_group":[],"created_at":"2026-03-03 11:09:25"}}