{"problem":{"name":"[JOI Open 2018] 木琴 / Xylophone","description":{"content":"木琴是一种乐器，人可以通过敲击木条来演奏它。单个木条总是发出同样音高的音，因此一个木琴包含不同种音高的木条。 JOI 君买了一个有 $N$ 个木条的木琴。这 $N$ 个木条排成一排，从左到右编号为 $1$ 到 $N$。编号为 $i\\ (1\\le i\\le N)$ 的木条能发出音高为 $A_i\\ (1\\le A_i\\le N)$ 的音。不同的木条发出不同音高的音。他知道音高最低的木条要比音高最高的","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9599"},"statements":[{"statement_type":"Markdown","content":"木琴是一种乐器，人可以通过敲击木条来演奏它。单个木条总是发出同样音高的音，因此一个木琴包含不同种音高的木条。\n\nJOI 君买了一个有 $N$ 个木条的木琴。这 $N$ 个木条排成一排，从左到右编号为 $1$ 到 $N$。编号为 $i\\ (1\\le i\\le N)$ 的木条能发出音高为 $A_i\\ (1\\le A_i\\le N)$ 的音。不同的木条发出不同音高的音。他知道音高最低的木条要比音高最高的编号小。\n\n因为 JOI 君不知道每个木条的音高是什么，他决定研究这些木条的音高。\n\nJOI 有一种独特的音感，当他连续听到多个音时，他能分辨出最高音和最低音差多少。他可以一次敲击一些木条，然后听它们发出的声音。也就是说，对于两个整数 $s$ 和 $t\\ (1\\le s\\le t\\le N)$，他可以连续敲击编号从 $s$ 到 $t$​ 的木条，以知道 $A_s,A_{s+1},\\ldots ,A_t$​ 中最大值与最小值的差。\n\n他想在 $10\\ 000$ 次敲击之内知道每个木条的音高。\n\n---\n\n**【实现细节】**\n\n你需要实现函数 `solve` 以求出每个木条的音高。\n\n- `solve(N)`\n\n  - $N$：木条的数量。\n  - 这个函数每个测试点调用恰好一次。\n\n你的程序可以调用评分器实现的如下函数。\n\n- `query(s, t)`\n\n  这个函数返回在给定区间中木条音高最大值与最小值的差。\n\n  - $s, t$：$s$ 是要敲击的木条区间中第一个数，$t$ 是最后一个数。也就是说，你需要敲击编号在 $[s,t]$ 区间内的所有木条。\n  - 必须保证 $1\\le s\\le t\\le N$。\n  - 你不能调用 `query` 函数超过 $10\\ 000$ 次。\n  - 如果上述条件不满足，你的程序会被判为 **Wrong Answer**。\n\n- `answer(i, a)`\n\n  你的程序应当用这个函数回答每个木条的音高。\n\n  - $i, a$：这意味着你回答了 $A_i$ 的值为 $a$，其中 $A_i$ 指木条 $i$ 的音高。\n  - 必须保证 $1\\le i\\le N$。\n  - 你不能对于相同的 $\\texttt i$ 调用超过一次这个函数。\n  - 你必须在函数 $\\texttt{solve}$ 结束前调用恰好 $N$ 次此函数。\n  - 如果上述条件不满足，你的程序会被判为 **Wrong Answer**。\n  - 如果你的回答与实际音高有不同，你的程序会被判为 **Wrong Answer**。\n\n暂不支持 Java 与 Pascal 提交的测评。\n\n## Background\n\n**特别提醒，由于洛谷交互机制的特殊性，你不能在程序中引用 `xylophone.h`，而需要把 `xylophone.h` 中的内容加入文件的开头。即，在程序中 `solve` 函数的前面加入以下几行语句：**\n\n```cpp\nvoid solve(int N);\nint query(int s, int t);\nvoid answer(int i, int a);\n```\n\n**同时不建议使用 C++14(GCC 9) 提交本题，建议选择 C++17 或者更高的语言版本提交。**\n\n[samples]\n\n## Note\n\n**【样例交互】**\n\n一个对于 $N=5,(A_1,A_2,A_3,A_4,A_5)=(2,1,5,3,4)$ 的样例交互过程如下。\n\n|          调用           |   返回值   |\n| :---------------------: | :--------: |\n| $\\texttt{query(1, 5)}$  |            |\n|                         |    $4$     |\n| $\\texttt{answer(1, 2)}$ |            |\n| $\\texttt{query(3, 5)}$  |  |\n|                         |    $2$     |\n| $\\texttt{answer(2, 1)}$​ |            |\n| $\\texttt{answer(3, 5)}$​ |  |\n| $\\texttt{answer(5, 4)}$​ |            |\n| $\\texttt{answer(4, 3)}$​ |  |\n\n**【数据范围】**\n\n所有子任务满足以下限制：\n\n- $1\\le A_i\\le N\\ (1\\le i\\le N)$\n- $A_i\\neq A_j\\ (1\\le i<j\\le N)$\n- 对于满足 $A_i=1,A_j=N$ 的 $i$ 和 $j$，满足 $i<j$​。\n\n本题有三个子任务。子任务分值及附加限制如下表所示：\n\n| 子任务编号 | 分值 |        $N$         |\n| :--------: | :--: | :----------------: |\n|    $1$     | $11$ |  $2\\le N\\le 100$   |\n|    $2$     | $36$ | $2\\le N\\le 1\\ 000$ |\n|    $3$     | $53$ | $2\\le N\\le 5\\ 000$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9599","tags":["2018","交互题","Special Judge","O2优化","JOI（日本）"],"sample_group":[],"created_at":"2026-03-03 11:09:25"}}