#[2714].「BalkanOI 2018 Day2」Popa

内存限制：256 MB 时间限制：1000 ms

翻译自 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

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++ 语言使用函数交互，其他语言可以通过 IO 交互来完成本题。如需使用 IO 交互，请参考「使用 IO 交互」部分。

选手应包含头文件 popa.h。选手需实现如下函数：

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$ 次。我们建议谨慎使用全局变量。

选手可以调用如下函数：

int query(int a, int b, int c, int d);

这个函数当且仅当 $\gcd[a,b]=\gcd[c,d]$ 时返回 $1$，其中 $0\le a\le b<n,0\le c\le d<N$，否则返回 $0$。

你的程序可以使用标准输入输出与交互器交互，格式如下。

在程序的开始，你应从标准输入读取一个整数 $T$，表示测试数据组数。

接下来开始进行每组数据的交互。在每组数据交互开始，你应从标准输入读取一个整数 $N$，意义同题目描述。接下来，如需调用 query 函数，你的程序应先输出一个 ?，后输出四个整数 $a,b,c,d$，意义同「交互」一节中函数的四个参数。整数与 ?，整数与整数之间用一个空格分隔；如果 solve 函数返回，你的程序应先输出形如 ! r 的一行，$r$ 表示 solve 函数的返回值。接下来输出两行长度为 $N$ 的整数数列，第一行按顺序输出 Left 数组中的元素，第二行按顺序输出 Right 数组中的元素。任意两个整数之间用一个空格隔开。

请不要忘记对于每行，都要输出换行符，并刷新标准输出缓冲区。

子任务编号	限制	分值
$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$

2714 「BalkanOI 2018 Day2」Popa

题目描述

交互

使用 IO 交互

样例

评分