CF2053D.Refined Product Optimality

作为测试者，当我的解答在测试时与样例输出不一致时，我首先会怀疑出题人。

—— Chris，一条评论

虽然 Iris 偶尔会出一些解答可能有误的题目，但她仍坚持用自己的想象力创造题目；毕竟，每个人都在用自己的固执走在路上……就像以往一样，Iris 又出了一道题，并且给出了一个错误的解答，但 Chris 总是要来拯救它！现在你要扮演 Chris 的角色：

• Chris 得到两个长度为 $n$ 的整数数组 $a$ 和 $b$。
• Iris 对 $b$ 进行任意重排后，关注 $P = \prod\limits_{i=1}^n \min(a_i, b_i)$ 的最大可能取值。注意，她只关心 $P$ 的最大值，并不会真的重排 $b$。
• 接下来会有 $q$ 次修改。每次修改由两个整数 $o$ 和 $x$ 表示（$o$ 只能为 $1$ 或 $2$，$1 \leq x \leq n$）。如果 $o=1$，则将 $a_x$ 增加 $1$；否则，将 $b_x$ 增加 $1$。
• Iris 会在 $q+1$ 个时刻询问 Chris $P$ 的最大值：第一次是在所有修改之前，之后每次修改后都要询问一次。
• 由于 $P$ 可能非常大，Chris 只需要输出 $P$ 对 $998\,244\,353$ 取模的结果。

Chris 很快就解决了这个问题，但他太累了睡着了。除了感谢 Chris，现在轮到你来编写程序，计算给定输入数据的答案。

注意：由于输入输出数据量较大，你可能需要对本题进行优化。

例如，在 C++ 中，只需在 main() 函数开头加入如下代码即可：

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
}

每组测试数据包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq q \leq 2 \cdot 10^5$），分别表示数组长度和操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 5 \cdot 10^8$），表示数组 $a$。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 5 \cdot 10^8$），表示数组 $b$。

接下来 $q$ 行，每行包含两个整数 $o$ 和 $x$（$o \in \{1, 2\}$，$1 \leq x \leq n$），表示一次操作。

保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $4 \cdot 10^5$。

对于每个测试用例，输出 $q+1$ 个整数，表示 Chris 计算出的答案，对 $998\,244\,353$ 取模。

在第一个测试用例中：

• 修改前，Chris 可以将 $b$ 重排为 $[1, 2, 3]$，此时 $P = \prod\limits_{i=1}^n \min(a_i, b_i) = 1 \cdot 1 \cdot 2 = 2$。可以证明这是最大值。例如，如果 Chris 将 $b$ 重排为 $[2, 3, 1]$，那么 $P = 1 \cdot 1 \cdot 1 = 1 < 2$，不是最优解。
• 第一次修改后，Chris 仍可以将 $b$ 重排为 $[1, 2, 3]$，此时 $P = 1 \cdot 1 \cdot 3 = 3$，达到最大值。
• 第二次修改后，Chris 可以将 $b$ 重排为 $[2, 2, 3]$，此时 $P = 1 \cdot 1 \cdot 3 = 3$，达到最大值。
• 第三次修改后，Chris 可以将 $b$ 重排为 $[2, 2, 3]$，此时 $P = 6$，达到最大值。
• 第四次修改后，Chris 可以将 $b$ 重排为 $[2, 2, 4]$，此时 $P = 6$，达到最大值。

由 ChatGPT 4.1 翻译