#5739. 「OOI 2026 Day2」装饰

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2026 Day2 T3 「Украшение」 / 「Decoration」。

在 Closed Olympiad 的筹备过程中，组织者决定装饰一下赛场。为此，他们在墙壁的一条直线上钉了 $2n$ 个小桩。所有小桩的位置各不相同。组织者在这些小桩之间拉了 $n$ 根绳子，其中第 $i$ 根绳子连接着距离墙头 $l_i$ 和 $r_i$ 处的两个桩 $(l_i < r_i)$。已知每个小桩上都恰好系着一根绳子。

你可以对这些绳子进行重连操作。一次重连操作的步骤如下：选择两根绳子 $(l_i, r_i)$ 和 $(l_j, r_j)$，将它们从桩上解开，然后将这四个腾出来的桩重新配对，拉起两根新的绳子（即每个桩仍需被使用一次）。

如果一个绳子集合中包含 $k$ 根绳子，且该集合内的任意两根绳子都相交，则称该配置方案的美感度至少为 $k$。如果两个闭区间 $[l_i, r_i]$ 和 $[l_j, r_j]$ 至少有一个公共点，则认为这两根绳子相交。需要注意的是，如果一个配置方案的美感度为 $k$，那么它的美感度同时也至少为 $k-1, k-2, \dots, 0$。

竞赛组织者提出了 $q$ 个询问，每个询问都要求通过若干次重连操作获得具有特定美感度的配置方案。在第 $i$ 个询问中，他们希望获得的美感度至少为 $k_i$。对于每个询问，请计算达成目标所需的最少重连操作次数。询问之间是相互独立的，即一个询问中所做的重连操作不会保留到另一个询问中。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \leq q \leq n \leq 200000)$，分别表示绳子的数量和询问的数量。

接下来的 $n$ 行描述初始的绳子配置。其中第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ $(1 \leq l_i < r_i \leq 10^9)$，表示第 $i$ 根绳子连接的两个桩的位置。保证每个桩在输入中只出现一次。

最后一行包含 $q$ 个整数 $k_1, k_2, \dots, k_q$ $(1 \leq k_i \leq n)$，表示组织者在各询问中要求达到的美感度。保证所有的 $k_i$ 各不相同。

输出格式

对于每个询问，输出一个非负整数，表示为了使绳子配置方案达到要求的美感度所需的最少重连操作次数。

保证对于每个询问，总可以通过有限次重连操作达成目标。

样例

输入

6 6
25 30
15 29
7 12
8 14
4 5
16 23
1 2 3 4 5 6

输出

0 0 1 1 2 3

在第一个样例中，绳子的初始配置如下：

由于绳子 $3$ 和绳子 $4$ 已经相交，因此为了获得至少为 $1$ 或 $2$ 的美感度，不需要进行任何操作。

为了获得 $3$ 或 $4$ 的美感度，可以对绳子 $2$ 和 $5$ 应用一次重连操作，得到新绳子 $(4, 29)$ 和 $(5, 15)$。

为了获得 $5$ 的美感度，可以额外对绳子 $3$ 和 $6$ 应用一次重连，得到 $(7, 16)$ 和 $(12, 23)$。

若要使所有 $6$ 根绳子都互相相交，可以分别对绳子 $1$ 和 $5$、绳子 $2$ 和 $3$、绳子 $4$ 和 $6$ 进行重连操作，得到如下配置：

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。