← 返回题目列表

Codeforces · 2035/G2

G2. 去学习吧! (困难版)

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

简单版和困难版之间的区别在于 $$$n$$$ 的约束以及 $$$n$$$ 的总和。在此版本中,$$$n \leq 3\cdot 10^5$$$ 且$$$n$$$ 之和不超过$$$10^6$$$。只有解决了两个版本的问题,你才能进行黑客攻击。

好吧,好吧,让我们看看贝西是如何管理她的财务的。看来她是在战壕里了!幸运的是,她正在申请 Moogle 的工作来解决这个问题。 Moogle 面试需要对晦涩的算法和复杂的数据结构有深入的了解,但 Bessie 从 LGM 那里得到了关于她必须学习的确切内容的提示。

Bessie 编写了以下代码,以二分查找可能未排序的数组 $$$[a_1, a_2,\ldots,a_n]$$$ 中的某个元素 $$$k$$$ 以及 $$$n$$$ 元素。

Bessie 通过 $$$m$$$ ($$$1 \leq m \leq n$$$) 测试向 Farmer John 的问题提交了代码。第 $$$i$$$ 测试的形式为 $$$(x_i, k_i)$$$ ($$$1 \leq x, k \leq n$$$)。保证所有 $$$x_i$$$ 都是不同的,并且所有 $$$k_i$$$ 都是不同的。

如果满足以下条件,则测试 $$$i$$$ 是正确的:

1. 数组中的第 $$$x_i$$$ 个元素是 $$$k_i$$$。
2. 如果Bessie 对$$$k_i$$$ 调用上述代码所示的二分查找,它将返回$$$x_i$$$。

同一个阵列上的所有 $$$m$$$ 测试可能不可能都是正确的,因此 Farmer John 将删除其中的一些测试,以便 Bessie 可以交流。令 $$$r$$$ 为删除的最小测试,以便存在一个数组 $$$[a_1, a_2,\ldots,a_n]$$$ 且 $$$1 \leq a_i \leq n$$$ 使得所有剩余测试都是正确的。

除了查找 $$$r$$$ 之外,Farmer John 还希望您使用 $$$1 \leq a_i \leq n$$$ 来计算数组 $$$[a_1, a_2,\ldots,a_n]$$$ 的数量,以便存在一种方法可以准确删除 $$$r$$$ 测试,以便所有剩余测试都是正确的。由于这个数字可能非常大,请对 $$$998\,244\,353$$$ 求模。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq m \leq n \leq 3 \cdot 10^5$$$) 表示数组的数量和测试的数量。

以下 $$$m$$$ 行每行包含两个整数,描述测试。第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$k_i$$$ ($$$1 \leq x_i, k_i \leq n$$$) 表示测试的索引和值。保证所有 $$$x_i$$$ 都是不同的,并且所有 $$$k_i$$$ 都是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出两个整数, $$$r$$$ - 删除的最少测试,以便存在一个数组,以便所有剩余的测试都是正确的,以及数组的数量,以便可以删除 $$$r$$$ 测试以使所有剩余的测试正确模 $$$998\,244\,353$$$。

示例

输入 #1

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

输出 #1

0 1
1 3

输入 #2

3
6 6
1 3
2 5
3 1
4 2
5 4
6 6
30 8
19 22
6 12
12 1
28 27
3 4
14 25
29 14
11 15
300000 1
5 10

输出 #2

3 78
3 839271911
0 702730519

注意

考虑第一个例子。

在第一个测试用例中,数组 $$$[1,2,2,3,4]$$$ 满足所有 $$$m$$$ 测试,因此 Bessie 必须删除的最小测试数量为 $$$0$$$。请注意,这也是唯一满足所有 $$$m$$$ 测试的数组。

在第二个测试用例中,Bessie 必须删除的最小测试数量为 $$$1$$$。 Bessie 唯一可以删除的测试是 $$$(2,5)$$$。如果 Bessie 删除测试 $$$(2,5)$$$,则满足剩余 $$$m-1$$$ 测试的数组为 $$$[2,2,3,1,4]$$$、$$$[2,2,3,2,4]$$$、$$$[2,2,3,3,4]$$$。