2354: [IOI2020]植物比较

植物学家 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],\dots ,r[n-1]$ 的值。

对于每对需要比较的植物 $x$ 和 $y$（$x$ 和 $y$ 不同），判定它们符合以下哪种情况：

• 植物 $x$ 一定比植物 $y$ 高：对于任意一组符合数组 $r$ 且互不相同的高度 $h[0],\dots h[n-1]$，都有$h[x]>h[y]$。
• 植物 $x$ 一定比植物 $y$ 矮：对于任意一组符合数组 $r$ 且互不相同的高度 $h[0],\dots h[n-1]$，都有 $h[x]<h[y]$。
• 该比较没有定论：以上两种情况都不成立。

实现细节

要求你实现以下函数：

void init(int k, std::vector<int> r) 

• $k$：决定每个 $r[i]$ 数值的连续植物的棵数。
• $r$：一个大小为 $n$ 的数组，其中 $r[i]$ 是植物 $i$ 顺时针方向的后$k-1$ 棵植物中比它高的棵数。
• 该函数恰好被调用一次，且在对 compare_plants 的任何调用前。

int compare_plants(int x, int y) 

• $x,y$ ：待比较的植物的编号。
• 该函数应该返回：
  • 1，如果植物 $x$ 一定比植物 $y$ 高，
  • $-1$，如果植物 $x$ 一定比植物 $y$ 矮，
  • $0$，如果该比较没有定论。
• 该函数恰好被调用 $q$ 次。

无

例 1
考虑以下调用：

init(3, [0, 1, 1, 2])
假设评测程序调用了 compare_plants(0, 2)。由 r[0]=0 可以推断植物 2 不比植物 0 高，因此该调用应该返回1。

假设评测程序接下来调用了 compare_plants(1, 2)。由于对每组符合以上条件的植物高度，都有植物 1 比物 2 矮，因此该调用应该返回 −1。

例 2
考虑以下调用：

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≤k≤n≤200 000
1≤q≤200 000
0≤r[i]≤k−1（对所有 0≤i≤n−1）
0≤x<y≤n−1
存在一组或多组 互不相同的高度 符合数组 r 记录的情况

子任务
1.（5 分）k=2
2.（14 分）n≤5000,2⋅k>n
3.（13 分）2⋅k>n
4.（17 分）每次 compare_plants 调用的正确答案是 1 或 −1
5.（11 分）n≤300,n⋅(n−1)/2
​6.（15 分）每次调用 compare_plants 时有 x=0
7.（25 分）没有附加约束条件