[IOI2020] 植物比较

**这是一道交互题**。 本题仅支持 C++ 系列语言，提交时不需要包含 `plant.h` 头文件。

植物学家 Hazel 参观过新加坡植物园的一个特别展览。在这次展览中，有 $n$ 棵 **高度互不相同** 的植物，它们排成了一个圆。这些植物按顺时针方向从 $0$ 到 $n-1$ 编号，植物 $n-1 $ 与植物 $0$ 是相邻的。 对于每棵植物 $i\ (0 \le i \le n-1$)，Hazel 将它与顺时针方向的后 $k-1$ 棵植物进行比较，记录下数值 $r[i]$ 以表示这 $k-1$ 棵植物中有多少棵的高度大于植物 $i$。因此，每个 $r[i]$ 的数值是由某段连续 $k$ 棵植物的相对高度决定的。 例如，假设 $n=5$，$k=3$，$i=3$。植物 $3$ 顺时针方向的后 $k-1=2$ 棵植物是植物 $4$ 和植物 $0$。如果植物 $4$ 比植物 $3$ 高，且植物 $0$ 比植物 $3$ 矮，那么 Hazel 将会记录 $r[3]=1$。 你可以假设 Hazel 记录的数值 $r[i]$ 都是正确的。也就是说，这些植物至少存在一组互不相同的高度符合 Hazel 所记录的数值。 本题要求你比较 $q$ 对植物的高度。由于你没有机会参观这次展览，你仅有的信息来源是 Hazel 的笔记本，其中记录了 $k$ 和序列 $r[0],\ldots, r[n-1]$ 的值。 对于每对需要比较的植物 $x$ 和 $y$（$x$ 和 $y$ 不同），判定它们符合以下哪种情况： - 植物 $x$ 一定比植物 $y$ 高：对于任意一组符合数组 $r$ 且互不相同的高度 $h[0],\ldots h[n-1]$，都有 $h[x] > h[y]$。 - 植物 $x$ 一定比植物 $y$ 矮：对于任意一组符合数组 $r$ 且互不相同的高度 $h[0],\ldots h[n-1]$，都有 $h[x]<h[y]$。 - 该比较没有定论：以上两种情况都不成立。 #### 实现细节 要求你实现以下函数： ```cpp void init(int k, std::vector<int> r) ``` - $k$：决定每个 $r[i]$ 数值的连续植物的棵数。 - $r$：一个大小为 $n$ 的数组，其中 $r[i]$ 是植物 $i$ 顺时针方向的后 $k-1$ 棵植物中比它高的棵数。 - 该函数恰好被调用一次，且在对 `compare_plants` 的任何调用前。 ```cpp int compare_plants(int x, int y) ``` - $x,y$ ：待比较的植物的编号。 - 该函数应该返回： - $1$，如果植物 $x$ 一定比植物 $y$ 高， - $-1$，如果植物 $x$ 一定比植物 $y$ 矮， - $0$，如果该比较没有定论。 - 该函数恰好被调用 $q$ 次。

#### 样例说明 #### 例 1 考虑以下调用： ```cpp init(3, [0, 1, 1, 2]) ``` 假设评测程序调用了 `compare_plants(0, 2)`。由 $r[0]=0$ 可以推断植物 $2$ 不比植物 $0$ 高，因此该调用应该返回 $1$。 假设评测程序接下来调用了 `compare_plants(1, 2)`。由于对每组符合以上条件的植物高度，都有植物 $1$ 比物 $2$ 矮，因此该调用应该返回 $-1$。 #### 例 2 考虑以下调用： ```cpp init(2, [0, 1, 0, 1]) ``` 假设评测程序调用了 `compare_plants(0, 3)`。由 $r[3]=1$ 可以推断植物 $0$ 比植物 $3$ 高，因此该调用应该返回 $1$。 假设评测程序接下来调用了 `compare_plants(1, 3)`。两组高度 $[3,1,4,2]$ 和 $[3,2,4,1]$ 都符合 Hazel 的观测记录，由于在第一种情况中植物 $1$ 比植物 $3$ 矮，而在第二种情况中它比植物 $3$ 高，因此该调用应该返回 $0$。 #### 约束条件 - $2\le k\le n\le 200\ 000$ - $1\le q\le 200\ 000$ - $0 \le r[i]\le k-1$（对所有 $0 \le i \le n-1$） - $0\le x<y\le n-1$ - 存在一组或多组 **互不相同的高度** 符合数组 $r$ 记录的情况 #### 子任务 1. （5 分）$k=2$ 2. （14 分）$n \le 5000,2 \cdot k > n$ 3. （13 分）$2 \cdot k > n$ 4. （17 分）每次 `compare_plants` 调用的正确答案是 $1$ 或 $-1$ 5. （11 分）$n\le 300, q\le \frac{n\cdot (n-1)}{2}$ 6. （15 分）每次调用 `compare_plants` 时有 $x=0$ 7. （25 分）没有附加约束条件 #### 评测程序示例 评测程序示例以如下格式读取输⼊数据： 第 $1$ 行：$n\ k\ q$ 第 $2$ 行：$r[0]\ r[1]\ \cdots\ r[n-1]$ 第 $3+i\ (0\le i\le q-1)$ 行：$x\ y$，表⽰第 $i$ 次调用 `compare_plants` 时的参数 评测程序示例以如下格式打印你的答案： 第 $1+i\ (0\le i\le q-1)$ 行：第 $i$ 次调用 `compare_plants` 的返回值