CF2261D2.Come Be My Friend, Don't Be So Scared (Hard Version)

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Note the unusual score distribution for D1 and D2. This problem is significantly more difficult than D1.

This is the hard version of the problem. The difference between the versions is that in this version, 0≤m≤2⋅1050 \le m \le 2 \cdot 10^5. You can hack only if you solved all versions of this problem.

You are hiding from the formidable Lord Verity.

There are nn possible hiding spots in a row, numbered from 11 to nn from left to right. You can hide in exactly one spot.

In order to find you, Lord Verity can install special detectors. Each detector covers a segment of consecutive spots and reports whether you are hiding in one of the spots in this segment. All detectors are activated simultaneously, so the segments of all detectors must be chosen before any report is known.

Lord Verity already has mm detectors; the ii-th of them covers the spots from lil_i to rir_i. Find the minimum number of additional detectors Lord Verity needs to install so that, wherever you hide, the reports of all detectors are enough to uniquely determine the spot that you are hiding in. You also need to find a way to install them.

注意 D1 和 D2 的分数分布非同寻常。本题显著难于 D1。

本题为该问题的困难版本。两个版本的区别在于:在本版本中,0≤m≤2⋅1050 \le m \le 2 \cdot 10^5。仅当您已解决该问题的所有版本后,才可进行 Hack。

你正在躲避强大的维里蒂领主(Lord Verity)。

一排共有 nn 个可能的藏身点,从左到右依次编号为 11 到 nn。你恰好只能藏在一个点中。

为了找到你,维里蒂领主可以安装特殊的探测器。每个探测器覆盖一段连续的藏身点,并报告你是否藏在这段区间内的某个点中。所有探测器同时启动,因此必须在获知任何探测结果之前就选定所有探测器所覆盖的区间。

维里蒂领主目前已拥有 mm 个探测器;其中第 ii 个探测器覆盖从 lil_i 到 rir_i 的藏身点。请找出维里蒂领主还需额外安装的最少探测器数量,使得无论你藏在哪一个点中,所有探测器的报告结果都足以唯一确定你的藏身位置。同时,你还需给出一种具体的安装方案。

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041 \le t \le 10^4). The description of the test cases follows.

The first line of each test case contains two integers nn and mm (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5, 0≤m≤2⋅1050 \le m \le 2\cdot 10^5) — the number of hiding spots and the number of detectors Lord Verity already has.

The ii-th of the next mm lines contains two integers lil_i and rir_i (1≤li≤ri≤n1 \le l_i \le r_i \le n) — the ii-th detector covers the spots from lil_i to rir_i.

It is guaranteed that no two given detectors cover the same range of hiding spots.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052 \cdot 10^5, and the sum of mm across all test cases does not exceed 2⋅1052\cdot 10^5.

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1041 \le t \le 10^4)。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 nn 和 mm(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5,0≤m≤2⋅1050 \le m \le 2\cdot 10^5)——分别表示藏匿点的数量以及领主维里蒂已拥有的探测器数量。

接下来的 mm 行中,第 ii 行包含两个整数 lil_i 和 rir_i(1≤li≤ri≤n1 \le l_i \le r_i \le n)——表示第 ii 个探测器覆盖从 lil_i 到 rir_i 的藏匿点。

保证任意两个给定的探测器所覆盖的藏匿点区间互不相同。

保证所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5,且所有测试用例的 mm 之和不超过 2⋅1052 \cdot 10^5。

输出格式

For each test case, first output a single integer kk — the minimum number of additional detectors.

Then output kk lines. The jj-th of them should contain two integers uju_j and vjv_j (1≤uj≤vj≤n1 \le u_j \le v_j \le n), meaning that the jj-th additional detector covers the hiding spots from uju_j to vjv_j.

If there are multiple solutions, print any of them.

对于每个测试用例,首先输出一个整数 kk —— 所需额外探测器的最小数量。

然后输出 kk 行。其中第 jj 行应包含两个整数 uju_j 和 vjv_j(1≤uj≤vj≤n1 \le u_j \le v_j \le n),表示第 jj 个额外探测器覆盖从 uju_j 到 vjv_j 的藏匿点。

若存在多种解法,输出任意一种即可。

输入输出样例

  • 输入#1

    7
    1 0
    2 0
    3 0
    5 2
    2 2
    4 4
    8 7
    1 2
    2 3
    3 4
    4 5
    5 6
    6 7
    7 8
    5 2
    2 3
    1 5
    4 2
    1 2
    3 4

    输出#1

    0
    1
    1 1
    2
    1 1
    2 2
    2
    1 3
    1 1
    0
    2
    1 4
    1 2
    1
    2 3

说明/提示

In the first test case, since there is only one hiding spot, Lord Verity knows you must be hiding there. No detectors are required.

In the second test case, there are two possible hiding spots. Lord Verity can install one detector with u=v=1u=v=1, which tells him if you are hiding in position 11 or not. Therefore, he can uniquely determine whether you are hiding in position 11 or 22 depending on the result.

In the fifth test case, we can show that Lord Verity can uniquely determine which hiding spot you are in with just the existing detectors.

在第一个测试用例中,由于只有一个藏身之处,维里蒂领主知道你必定藏在那里,因此无需安装任何探测器。

在第二个测试用例中,存在两个可能的藏身之处。维里蒂领主可以安装一个探测器,其参数为 u=v=1u=v=1,该探测器可告诉他你是否藏在位置 11。因此,他可根据探测结果唯一确定你藏在位置 11 还是位置 22。

在第五个测试用例中,我们可以证明:仅利用已有的探测器,维里蒂领主即可唯一确定你所藏的具体位置。

输入解题思路,AI测评打分。不知道怎么写?

首页