P14909 [NHSPC 2024] 区间最大独立集询问

$\textcolor{red}{\textbf{这是一道交互题，请使用 C++17 或者以上的语言标准提交。}}$

小云最近在学习「最大权重独立集（Maximum-Weight Independent Set, MWIS）」的算法。 根据定义，一张无向图里的顶点子集合 $I$ 要被称作「独立集」的话，需要满足 $I$ 集合中任两个顶点在原图上皆互不相邻的条件。而「最大权重独立集」则是所有可能的「独立集」中，点权重总和最大的一组。 今天小云发现，假如这张无向图是一条链（Chain）的话，那要找到「最大权重独立集」变得超级简单！他向小成分享这件事之后，小成却反问:「那你知道怎么有效率地回答一条链上面的『区间最大权重独立集询问』吗？」 经过一番研究后，小云发现，即使在不知道链上每个节点的具体权重下，也能找到它的最大权重独立集，甚至能用来解决区间询问。于是，他列了以下这道难题给小成： 「给定一条包含 $n$ 个顶点编号为 $1, 2, \ldots, n$ 的链（chain），其中对于任何的 $1 \leq i < n$，顶点 $i$ 与顶点 $i+1$ 之间皆有一条无向边，且对于任何 $1 \leq i \leq n$，顶点 $i$ 的权重为一个正整数 $w_i$，请回答 $q$ 个『区间最大权重独立集询问 (Range MWIS Query)』。」 「在区间最大权重独立集询问中，对于满足 $1 \leq l \leq r \leq n$ 的任意区间，你必须回答我顶点 $l, l + 1, \ldots, r$ 之间的最大权重独立集是什么。」 小云接着补充。 「当然，在一无所知的情况下不可能解决这个问题，所以我允许你执行数次『权重和比较询问』：任选两个顶点的子集，我会告诉你哪一个子集的顶点权重和比较大。」 请协助小成，在执行**尽量少**次『顶点子集权重比较』的情况下，回答所有待询问区间里的最大权重独立集！ ### 实现细节 你需要实现两个函数 `init()` 与 `range_MWIS_query()`： ```cpp void init(int n); ``` * 对于每一组测试数据，正式评分程序会调用你实现的 `init()` 函数恰好 $1$ 次。 * $n$ 代表顶点的数量。 ```cpp std::vector range_MWIS_query(int l, int r); ``` * 对于每一组测试数据，正式评分程序会调用你实现的 `range_MWIS_query()` 函数恰好 $q$ 次。 * 保证在调用完 `init()` 后才会调用此函数。 * `range_MWIS_query()` 需要返回一个数组 $x_1, x_2, \ldots, x_m$。 * 数组 $x$ 代表了该询问区间的最大权重独立集包含的顶点编号。 * 对于所有 $1\le i \le m$，皆须保证 $l \leq x_i \leq r$。 * 对于所有 $1\le i < j \le m$，皆须保证 $|x_i - x_j| > 1$。 此外，在实现时可以调用 `compare_subsets()` 这个函数。 ```cpp bool compare_subsets(const std::vector& a, const std::vector& b); ``` * $a$ 是一个数组，其描述了 $\{1, 2, \ldots, n\}$ 的子集。 * $b$ 是一个数组，其描述了 $\{1, 2, \ldots, n\}$ 的子集。 * $a$ 内不能有重复的数字。 * $b$ 内不能有重复的数字。 * 若集合 $a$ 内的顶点的权重和比集合 $b$ 小，则该函数会返回布尔值 `true`，否则会返回布尔值 `false`。 * **示例评分程序**内的 `compare_subsets()` 实现与**实际评分程序**内的实现完全相同。 ### 交互范例 一个可能被评为 `Accepted` 的交互例子显示如下： | 评分程序端 | 参赛者端 | | ---- | ---- | | 调用 `init(` $5$ `)`。 | | | | 调用 `compare_subsets(` $[1]$, $[2]$ `)`。 | | 返回 `true`。 | | | | 调用 `compare_subsets(` $[3]$, $[4]$ `)`。 | | 返回 `false`。 | | | | 返回 `void()` | | 调用 `range_MWIS_query(`$2, 5$`)` | | | | 调用 `compare_subsets(` $[2, 5]$, $[1, 3, 5]$ `)`。 | | 返回 `true`。 | | | | 返回 $[2, 4]$ | | 调用 `range_MWIS_query(`$1, 5$`)` | | | | 返回 $[1, 3, 5]$ |

示例评分程序采用以下格式输入： $$\begin{aligned} &n \ q \\ &w_1 \ w_2 \ \ldots \ w_n \\ &l_1 \ r_1 \\ &l_2 \ r_2 \\ &\vdots \\ &l_q \ r_q \end{aligned}$$ 请注意，正式的评分程序一定不会采用以上格式输入。请不要自行处理输入输出。

示例评分程序首先调用 `init(`$n$`)`，接着示例评分程序会调用 $q$ 次 `range_MWIS_query(`$l_i, r_i$`)`。接着，若示例评分程序检测到从 `init` 或 `range_MWIS_query` 对 `compare_subsets` 的调用有任何不合法，此程序将输出 `Wrong Answer: msg ` 后并终止程序执行，其中 $msg$ 为下列其中之一的错误信息： - `Invalid vertex number: v`: 你的程序传入 `compare_subsets` 的集合中有不介于 $1\sim n$ 之间的数字 $v$。 - `Duplicate vertex numbers: v`: 你的程序传入 `compare_subsets` 的集合中有重复的数字 $v$。 否则，示例评分程序将会以下列格式印在标准输出中： $$\begin{aligned} &m_1 \\ &x_{1, 1} \ x_{1, 2} \ \ldots \ x_{1, m_1} \\ &m_2 \\ &x_{2, 1} \ x_{2, 2} \ \ldots \ x_{2, m_2} \\ &\vdots \\ &m_q \\ &x_{q, 1} \ x_{q, 2} \ \ldots \ x_{q, m_q} \\ &\text{Accepted:} \ Q_{init} \ Q_{query} \end{aligned}$$ 其中， - $m_i$ 为第 $i$ 次调用 `range_MWIS_query()` 时你返回的数组长度。 - $x_{i, j}$ 为第 $i$ 次调用 `range_MWIS_query()` 时你返回的数组的第 $j$ 项。 - $Q_{init}$ 与 $Q_{query}$ 为根据你的程序调用 `compare_subsets` 的次数得来的数值，详细定义请见评分说明栏位。

对于每一组测试数据，若你的程序在函数 `init()` 中调用 `compare_subsets` 的次数为 $x$、在第 $i$ 次 `range_MWIS_query()` 中调用 `compare_subsets` 的次数为 $y_i$，则定义 $Q_{init}$ 与 $Q_{query}$ 为： $$ \begin{cases} Q_{init} = \left\lceil \displaystyle\frac{x}{n} \right\rceil\\ Q_{query} = \displaystyle\max_{1 \leq i \leq q} y_i \end{cases} $$ 根据 $Q_{init}$ 与 $Q_{query}$，你将得到两个分数比重 $W_{init}$ 与 $W_{query}$： $$ W_{init} = \begin{cases} 1.0 & \text{ 若 $Q_{init}\le 3$；}\\ 1.0 - 0.07 \cdot (Q_{init} - 3) & \text{ 若 $3 < Q_{init} \le 10$；}\\ 0.5 - 0.04 \cdot (Q_{init} - 10) & \text{ 若 $10 < Q_{init} \le 20$；}\\ 0 & \text{ 若 $Q_{init} > 20$。} \end{cases} $$ $$ W_{query} = \begin{cases} 1.0 & \text{ 若 $Q_{query}\le 1$；}\\ 1.0 - 0.1 \cdot (Q_{query} - 1) & \text{ 若 $1 < Q_{query} \le 10$；}\\ 0 & \text{ 若 $Q_{query} > 10$。} \end{cases} $$ 你的最终比重 $W$ 会是两者相乘，也就是： $$ W = W_{init}\cdot W_{query} $$ 本题共有 3 组子任务，条件限制如下所示。 每一组可有一或多组测试数据，你在该子任务的得分为所有测试数据中分数比重 $W$ 的最小值，乘以该子任务的总分。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | 16 | $l = 1$。 | | 2 | 11 | 对于所有询问的区间 $[l, r]$，区间 $[1, r]$ 的最大权重独立集唯一且不包含顶点 $l + 1$。 | | 3 | 73 | 无额外限制。 | ### 数据范围 - $1\leq n\le2000$ - $1\leq q\le2000$ - $1\leq l\leq r\leq n$