简单版和困难版之间的区别在于 $$$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]$$$。