一、题意重述

给定两个长度为 $n$ 的数组 $a$ 和 $b$，可以任意重排数组 $b$，求

$$P=\prod_{i=1}^n \min(a_i,b'_i)$$

的最大值，其中 $b'$ 是 $b$ 的一个排列。

随后有 $q$ 次操作：

• $o=1,x$：将 $a_x$ 加 $1$
• $o=2,x$：将 $b_x$ 加 $1$

要求输出初始答案 + 每次操作后答案，共 $q+1$ 个结果，答案对 $998244353$ 取模。

数据范围：

• $1\le t\le 10^4$
• $\sum n,\sum q\le 4\times 10^5$
• $1\le a_i,b_i\le 5\times 10^8$

---

二、核心结论：最优配对策略

要最大化 $\prod\min(a_i,b_j)$，经典贪心策略为：

1. 将数组 $a$ 从小到大排序得到 $A$
2. 将数组 $b$ 从小到大排序得到 $B$
3. 按相同下标配对：$A_i \leftrightarrow B_i$

此时

$$\max P = \prod_{i=1}^n \min(A_i,B_i)$$

证明简述： 排序后两两配对是使 $\min$ 乘积最大的唯一最优方案，任何交叉配对都会让至少一对 $\min$ 变小，从而乘积更小。

---

三、整体思路

1. 预处理

   • 复制 $a,b$ 得到排序数组 $c,d$
   • 对 $c,d$ 分别升序排序
   • 计算初始乘积 $\prod_{i=1}^n\min(c_i,d_i)\bmod 998244353$

2. 动态维护答案 每次操作只会单点增加 $a_x$ 或 $b_x$：

   • 该元素在排序数组 $c$ 或 $d$ 中的位置可以用二分快速定位
   • 若该位置原来满足 $\min$ 由它贡献，则更新答案：乘旧值的逆元，再乘新值
   • 直接将排序数组中对应位置的值 $+1$，保持数组有序（因为只加 $1$，不会破坏有序性）

3. 模运算与逆元 因为要动态除以某个数，使用费马小定理求逆元：

   $$x^{-1}\equiv x^{MOD-2}\pmod{MOD}$$

---

四、标程关键细节解析

1. 快速幂求逆元

int qpow(int a, int x = MOD - 2) {
	int res = 1;
	for (; x; x >>= 1, a = 1ll * a * a % MOD)
		if (x & 1) res = 1ll * res * a % MOD;
	return res;
}

• 用途：计算 $a$ 在模 $998244353$ 下的乘法逆元
• 原理：$MOD$ 是质数，$a^{MOD-2}\equiv a^{-1}\pmod{MOD}$

2. 初始答案计算

sort(c + 1, c + n + 1);
sort(d + 1, d + n + 1);
for (int i = 1; i <= n; ++i)
    res = 1ll * res * min(c[i], d[i]) % MOD;

• $c$ 是 $a$ 的排序版，$d$ 是 $b$ 的排序版
• 按位配对求 $\min$ 并累乘得到初始最大乘积

3. 单点修改维护

以修改 $a_x$ 为例：

int p = upper_bound(c + 1, c + n + 1, a[x]) - c - 1;
if (c[p] < d[p])
    res = 1ll * res * qpow(c[p]) % MOD * (c[p] + 1) % MOD;
++a[x], ++c[p];

1. 二分定位 upper_bound 找到 $a[x]$ 在有序数组 $c$ 中的位置 $p$
2. 判断是否影响答案 只有当 $c[p]<d[p]$ 时，$\min(c_p,d_p)=c_p$，修改 $c_p$ 才会改变乘积
3. 更新答案$$res = res \times c_p^{-1} \times (c_p+1) \bmod MOD $$
4. 同步更新 原数组 $a[x]$ 与排序数组 $c[p]$ 同时 $+1$

修改 $b_x$ 逻辑完全对称。

---

五、复杂度分析

• 排序：$O(n\log n)$
• 每次操作：二分 $O(\log n)$，其余 $O(1)$
• 总复杂度：$O(\sum n\log n+\sum q\log n)$
• 完全满足 $\sum n,\sum q\le 4\times 10^5$ 的时限要求

---

六、正确性说明

1. 每次只 $+1$，排序数组仍保持有序，无需重新排序
2. 二分能精准定位到原元素在排序数组中的位置
3. 仅当该位置是 $\min$ 贡献者时才更新答案，保证结果正确
4. 模运算全程使用 $1LL$ 避免溢出，保证计算安全

---

七、标程运行流程（以样例1为例）

样例输入：

3 4
1 1 2
3 2 1

初始：

• $a=[1,1,2],\ b=[3,2,1]$
• 排序后 $c=[1,1,2],\ d=[1,2,3]$
• $\min$ 依次为 $1,1,2$，乘积 $1\times1\times2=2$

后续操作依次修改 $a_3,b_3,a_1,b_1$，程序动态维护乘积，最终输出：

2 3 3 6 6

与样例完全一致。