P9599 [JOI Open 2018] 木琴 / Xylophone

**特别提醒，由于洛谷交互机制的特殊性，你不能在程序中引用 `xylophone.h`，而需要把 `xylophone.h` 中的内容加入文件的开头。即，在程序中 `solve` 函数的前面加入以下几行语句：** ```cpp void solve(int N); int query(int s, int t); void answer(int i, int a); ``` **同时不建议使用 C++14(GCC 9) 提交本题，建议选择 C++17 或者更高的语言版本提交。**

木琴是一种乐器，人可以通过敲击木条来演奏它。单个木条总是发出同样音高的音，因此一个木琴包含不同种音高的木条。 JOI 君买了一个有 $N$ 个木条的木琴。这 $N$ 个木条排成一排，从左到右编号为 $1$ 到 $N$。编号为 $i\ (1\le i\le N)$ 的木条能发出音高为 $A_i\ (1\le A_i\le N)$ 的音。不同的木条发出不同音高的音。他知道音高最低的木条要比音高最高的编号小。 因为 JOI 君不知道每个木条的音高是什么，他决定研究这些木条的音高。 JOI 有一种独特的音感，当他连续听到多个音时，他能分辨出最高音和最低音差多少。他可以一次敲击一些木条，然后听它们发出的声音。也就是说，对于两个整数 $s$ 和 $t\ (1\le s\le t\le N)$，他可以连续敲击编号从 $s$ 到 $t$​ 的木条，以知道 $A_s,A_{s+1},\ldots ,A_t$​ 中最大值与最小值的差。 他想在 $10\ 000$ 次敲击之内知道每个木条的音高。 --- **【实现细节】** 你需要实现函数 `solve` 以求出每个木条的音高。 - `solve(N)` - $N$：木条的数量。 - 这个函数每个测试点调用恰好一次。 你的程序可以调用评分器实现的如下函数。 - `query(s, t)` 这个函数返回在给定区间中木条音高最大值与最小值的差。 - $s, t$：$s$ 是要敲击的木条区间中第一个数，$t$ 是最后一个数。也就是说，你需要敲击编号在 $[s,t]$ 区间内的所有木条。 - 必须保证 $1\le s\le t\le N$。 - 你不能调用 `query` 函数超过 $10\ 000$ 次。 - 如果上述条件不满足，你的程序会被判为 **Wrong Answer**。 - `answer(i, a)` 你的程序应当用这个函数回答每个木条的音高。 - $i, a$：这意味着你回答了 $A_i$ 的值为 $a$，其中 $A_i$ 指木条 $i$ 的音高。 - 必须保证 $1\le i\le N$。 - 你不能对于相同的 $\texttt i$ 调用超过一次这个函数。 - 你必须在函数 $\texttt{solve}$ 结束前调用恰好 $N$ 次此函数。 - 如果上述条件不满足，你的程序会被判为 **Wrong Answer**。 - 如果你的回答与实际音高有不同，你的程序会被判为 **Wrong Answer**。 暂不支持 Java 与 Pascal 提交的测评。

无

无

**【样例交互】** 一个对于 $N=5,(A_1,A_2,A_3,A_4,A_5)=(2,1,5,3,4)$ 的样例交互过程如下。 | 调用 | 返回值 | | :---------------------: | :--------: | | $\texttt{query(1, 5)}$ | | | | $4$ | | $\texttt{answer(1, 2)}$ | | | $\texttt{query(3, 5)}$ | | | | $2$ | | $\texttt{answer(2, 1)}$​ | | | $\texttt{answer(3, 5)}$​ | | | $\texttt{answer(5, 4)}$​ | | | $\texttt{answer(4, 3)}$​ | | **【数据范围】** 所有子任务满足以下限制： - $1\le A_i\le N\ (1\le i\le N)$ - $A_i\neq A_j\ (1\le i