← 返回题目列表

Codeforces · 1366/B

B. 随机播放

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 整数 $$$a_1$$$、$$$a_2$$$、...、$$$a_n$$$ 组成的数组。最初$$$a_x = 1$$$,所有其他元素都等于$$$0$$$。

您必须执行 $$$m$$$ 操作。在第 $$$i$$$ 操作期间,您选择两个索引 $$$c$$$ 和 $$$d$$$,使得 $$$l_i \le c, d \le r_i$$$,并交换 $$$a_c$$$ 和 $$$a_d$$$。

计算索引 $$$k$$$ 的数量,以便可以选择操作使得最终 $$$a_k = 1$$$ 。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例的描述。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$x$$$ 和 $$$m$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le m \le 100$$$; $$$1 \le x \le n$$$)。

接下来的 $$$m$$$ 行包含操作的描述;第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$)。

输出

对于每个测试用例,打印一个整数 - 索引 $$$k$$$ 的数量,以便可以选择操作,以便最终 $$$a_k = 1$$$。

示例

输入 #1

3
6 4 3
1 6
2 3
5 5
4 1 2
2 4
1 2
3 3 2
2 3
1 2

输出 #1

6
2
3

注意

在第一个测试用例中,对于每个 $$$k$$$ 可以实现 $$$a_k = 1$$$。为此,您可以使用以下操作:

1. 交换 $$$a_k$$$ 和 $$$a_4$$$;
2. 交换 $$$a_2$$$ 和 $$$a_2$$$;
3. 交换 $$$a_5$$$ 和 $$$a_5$$$。

在第二个测试用例中,只有 $$$k = 1$$$ 和 $$$k = 2$$$ 是可能的答案。要实现 $$$a_1 = 1$$$,您必须在第二次操作期间交换 $$$a_1$$$ 和 $$$a_1$$$。要实现 $$$a_2 = 1$$$,您必须在第二次操作期间交换 $$$a_1$$$ 和 $$$a_2$$$。