这是官方题解的 AI 中文翻译。

对于一个排列 $p$，我们定义 $a(p)$ 为所有角 $\angle A_{p_{i-1}} A_{p_i} A_{p_{i+1}}$ 中锐角的数量。

任务 = $1$

你需要找到一个排列 $p$，使得 $a(p) = n - 2$。

可以通过 $O(n!)$ 的复杂度枚举所有排列。

对于点集随机的子任务，可以采用优化方法（后文将讨论）。

该情形的完整解法如下：

• 我们从 $A_1$ 作为第一个点，逐步构建排列。
• 在每一步，我们从剩余的点中选择 $A_{p_{i+1}}$，使得线段 $A_{p_i} A_{p_{i+1}}$ 的长度最大，即选择距离最远的点。
• 注意到 $\angle A_{p_i} A_{p_{i+1}} A_{p_{i+2}}$ 是锐角，因为 $A_{p_i} A_{p_{i+1}} \geq A_{p_{i}} A_{p_{i+2}}$。
• 由此我们得到一个排列，使得 $a(p) = n - 2$，达到了最大值。

优化思路

对于点集随机的子任务，优化方法非常有效！

我们需要最小化函数 $f(p) = -a(p)$（当 $task=1$ 时），或 $f(p) = |a(p) - k|$（当 $task=3, 4$ 时）。

例如，我们可以随机交换排列中的两个元素，并在 $O(1)$ 的时间内重新计算该函数。然后通过局部优化或模拟退火方法，找到答案。

为了覆盖所有 $k$ 的取值，可以利用“几乎离散的连续性”。局部改变排列时，函数的变化不会超过 $6$。因此，我们可以先最小化该函数，再最大化它。这样，如果我们记录下所有得到的答案，就能快速覆盖所有需要的 $k$。

$x_i < x_{i+1}, y_i < y_{i+1}$

关于单调性的主要思想：

• 假设有三个点 $A_1 (x_1, y_1)$、$A_2 (x_2, y_2)$、$A_3 (x_3, y_3)$，满足 $x_1 < x_2 < x_3$ 或 $x_1 > x_2 > x_3$，且 $y_1 < y_2 < y_3$ 或 $y_1 > y_2 > y_3$。
• 那么，$\angle A_1 A_2 A_3$ 始终是钝角，而 $\angle A_2 A_1 A_3$ 与 $\angle A_2 A_3 A_1$ 始终是锐角。

因此，解法如下：

• 若要求最大化，我们只需考虑排列 $1, n, 2, n - 1, 3, n - 2, \ldots$。
• 若要求得到特定的 $k$，可以采用如下排列：

$$\left[ 1, k + 2, 2, k + 1, 3, k, \ldots \right], \left[ k + 3, k + 4, \ldots, n \right]$$

或

$$\left[ k + 2, 1, k + 1, 2, k, 3, \ldots \right], \left[ k + 3, k + 4, \ldots, n \right]$$

单调子序列

• 任意长度为 $n \leq 2 x^2$ 的排列，可以被划分为不超过 $2x$ 个单调（递增或递减）子序列。算法如下：
• 在 $O(n \log n)$ 的时间内找到最长递增子序列，长度为 $k$。
• 若 $k \leq 2x$，则我们自动得到了 $k$ 个递增子序列的划分（例如，利用二分查找算法）。
• 若 $k > 2x$，则移除该递增子序列，剩余排列长度不超过 $2 x^2 - 2x - 1 \leq (x-1)^2$。
• 总的构造时间为 $O(n \sqrt{n} \log n)$。

任务 = $2$

• 单调子序列很有用——我们可以制造大量钝角。
• 我们将点集划分为不超过 $\sqrt{2n} \leq 400$ 个单调子序列。
• 可以将这些子序列连接起来，此时锐角的数量不会超过 $2 \sqrt{2n}$。

任务 = $3$

• 在单调子序列中，我们可以获得任意数量的锐角。
• 我们希望将各子序列的折线连接起来，问题在于连接处（锐角数量会不可预测地变化）。
• 如果我们在每个子序列中固定首、次、末、倒数第二个元素，则连接时锐角数量可预测。
• 现在可以获得任意 $k$，但会有一定的奇偶性限制（因为有固定元素）。
• 若多尝试几种随机方案，即可覆盖所有奇偶性。

任务 = $4$

• 我们构造类似的例子。
• 对所有例子一起，可以细致地计算哈希值。
• 上述方案可以直接得到任何 $k \in [5 \sqrt{2n}, n - 5 \sqrt{2n}]$。
• 通过细致分析连接情况，常数可以优化到 $2$。
• 总体复杂度为 $O(n \sqrt{n} \log n + q n)$。