P16369 [OOI 2026] Decoration

在准备面向中学生的闭门编程奥林匹克竞赛的过程中，组织者决定装饰礼堂。为此，他们在墙上沿着一条直线钉上了 $2n$ 个木桩。所有木桩均位于不同的位置。在它们之间，拉起了 $n$ 条绳子，其中第 $i$ 条绳子拉在距离墙的起点分别为 $l_i$ 和 $r_i$ 的两个木桩之间（$l_i < r_i$）。已知每个木桩上恰好系有一条绳子。 这些绳子可以进行一种称为 **重系** 的操作。在一次 **重系** 操作中，你可以选择两条绳子 $(l_i, r_i)$ 和 $(l_j, r_j)$，将它们从木桩上解下，然后用这四个释放出来的木桩恰好各一次地挂上两条新绳子。也就是说，从这四个释放的木桩中，形成两个新的配对，并在它们之间拉上新绳子。 如果线段 $[l_i, r_i]$ 与 $[l_j, r_j]$ 至少有一个公共点，则称拉在木桩 $(l_i, r_i)$ 和 $(l_j, r_j)$ 之间的绳子相交。如果存在一个包含 $k$ 条绳子的集合，其中的绳子两两相交，则称一个绳子配置的 **美观度** 至少为 $k$。注意，如果一个配置的美观度为 $k$，那么它的美观度也至少为 $k - 1,\ k - 2,\ \ldots,\ 0$。 奥林匹克竞赛的组织者有 $q$ 个查询，希望通过若干次 **重系** 操作来得到具有特定美观度的配置。在第 $i$ 个查询中，他们希望达到至少为 $k_i$ 的美观度。对于每个查询，组织者希望知道所需的最少 **重系** 操作次数。这些查询之间相互独立，这意味着查询之间的 **重系** 操作不会被保留。

第一行包含两个整数 $n$ 和 $q$（$1 \le q \le n \le 200\,000$）—— 绳子的数量以及查询的数量。 接下来的 $n$ 行描述绳子。第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i < r_i \le 10^9$）—— 第 $i$ 条绳子所连接的木桩的编号。保证每个木桩恰好出现一次。 再接下来一行包含 $q$ 个整数 $k_1$, $k_2$, $\ldots$, $k_q$（$1 \le k_i \le n$）—— 组织者查询中所期望的美观度大小。保证所有 $k_i$ 互不相同。

对于每个查询，输出一个非负整数 —— 为得到查询中所要求美观度的绳子配置，所需执行的最少 **重系** 操作次数。 保证对于每个查询，都可以通过执行若干次 **重系** 来达到所要求美观度的配置。

### 样例解释 在第一个例子中，绳子的初始配置如下： :::align{center}  ::: 由于绳子 3 和 4 已经相交，要达到美观度至少为 $1$ 和至少为 $2$ 不需要任何操作。 要达到美观度 $3$ 和 $4$，你可以对绳子 2 和 5 执行一次 **重系** 操作，得到绳子 $(4, 29)$ 和 $(5, 15)$。 :::align{center}  ::: 要达到美观度 $5$，你可以再对绳子 3 和 6 进行一次操作，得到 $(7, 16)$ 和 $(12, 23)$。 :::align{center}  ::: 要使所有 6 条绳子都相交，你可以对绳子 1 和 5、2 和 3、4 和 6 进行操作，得到如下配置： :::align{center}  ::: ### 计分 本题的测试数据分为 6 组。每组仅在通过该组内全部测试以及此前某些组的全部测试后，才能获得分数。注意，某些组不要求通过题面中的样例。 | 组别 | 分数 | 附加限制 | < | < | 必过组别 | 备注 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | $n$ | $q$ | $k_i$ | | | | $0$ | $0$ | -- | -- | -- | -- | 题面中的样例。 | | $1$ | $14$ | $n \le 100$ | -- | -- | $0$ | -- | | $2$ | $16$ | $n \le 3000$ | -- | -- | $0, 1$ | -- | | $3$ | $13$ | -- | -- | -- | -- | 绳子两两不相交。 | | $4$ | $25$ | -- | $q=1$ | $k_i = n$ | -- | -- | | $5$ | $17$ | -- | $q=1$ | $k_i \le 10$ | -- | -- | | $6$ | $15$ | -- | -- | -- | $0$ -- $5$ | -- | 翻译由 DeepSeek V4 Pro 完成