CF2035G2 Go Learn! (Hard Version)

本题的简单版与困难版的区别在于 $n$ 和 $n$ 的总和的限制。在本题中，$n \leq 3 \cdot 10^5$，且所有 $n$ 的总和不超过 $10^6$。只有在两种版本都通过后才能进行 hack。 让我们看看 Bessie 是如何管理她的财务的。她似乎陷入了困境！幸运的是，她正在申请 Moogle 的工作来解决这个问题。Moogle 的面试需要对冷门算法和复杂数据结构有深入了解，但 Bessie 从一位 LGM 那里得到了确切的学习建议。 Bessie 写了如下代码，试图在一个可能无序的数组 $[a_1, a_2, \ldots, a_n]$ 中用二分查找某个元素 $k$： ``` let l = 1 let h = n while l < h: let m = floor((l + h) / 2) if a[m] < k: l = m + 1 else: h = m return l ``` Bessie 将她的代码提交给 Farmer John 的问题，并有 $m$（$1 \leq m \leq n$）组测试。第 $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 能够 AC。设 $r$ 为需要移除的最少测试数，使得存在一个数组 $[a_1, a_2, \ldots, a_n]$，$1 \leq a_i \leq n$，使得剩下的所有测试都正确。 除了求 $r$，Farmer John 还希望你统计有多少个数组 $[a_1, a_2, \ldots, a_n]$，$1 \leq a_i \leq n$，存在一种移除恰好 $r$ 个测试的方法，使得剩下的测试都正确。由于答案可能很大，请输出对 $998\,244\,353$ 取模的结果。

第一行包含一个整数 $t$（$1 \leq t \leq 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,2,3,4]$ 能满足所有 $m$ 个测试，因此 Bessie 需要移除的测试数最少为 $0$。注意，这也是唯一能满足所有 $m$ 个测试的数组。 在第二个测试用例中，最少需要移除 $1$ 个测试。Bessie 唯一可以移除的测试是 $(2,5)$。如果移除测试 $(2,5)$，则能满足剩下 $m-1$ 个测试的数组有 $[2,2,3,1,4]$、$[2,2,3,2,4]$、$[2,2,3,3,4]$。 由 ChatGPT 4.1 翻译