題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟢 CF2053D. Refined Product Optimality

Problem Statement

題目簡述

給定兩個長度為 $n$ 的整數陣列 $A$ 和 $B$ 。我們可以任意重排 $B$ 。
你的目標是最大化 $P = \prod\limits_{i=1}^n \min(A_i, B_i)$ 。
題目共有 $q$ 次修改操作，每次操作會給定 $(o, x)$ ，若 $o=1$ 則將 $A_x$ 加 1，若 $o=2$ 則將 $B_x$ 加 1。
請輸出初始狀態以及每次修改後，可以得到的最大 $P$ 值（對 $998244353$ 取模）。

Constraints

約束條件

$1 \le n, q \le 2 \cdot 10^5$
$\sum n, \sum q \le 4 \cdot 10^5$
$1 \le a_i, b_i \le 5 \cdot 10^8$

思路：貪心 + 排序 + 二分查找

貪心：排序後配對最優

將 $A$ 和 $B$ 分別從小到大排序後，設排序後的陣列為 $C$ 和 $D$ ，則最大乘積為：

P = \prod_{i=1}^n \min(C_i, D_i)

為什麼排序後配對最優？

假設 $A, B$ 排序後分別為 $C, D$ 。若存在逆序對 $(i, j)$ ，即 $C_i \le C_j$ 但 $D_i > D_j$ 。

令 $a = C_i, b = C_j$ （故 $a \le b$ ）， $d = D_i, c = D_j$ （故 $c < d$ ）。比較兩種配對：

交換前（逆序）： $V_{pre} = \min(a, d) \times \min(b, c)$
交換後（同序）： $V_{post} = \min(a, c) \times \min(b, d)$

情況一：

c \ge a

此時 $d > c \ge a$ ，故 $\min(a, d) = a$ ， $\min(a, c) = a$ 。

$V_{pre} = a \times \min(b, c)$
$V_{post} = a \times \min(b, d)$

因為 $c < d$ ，所以 $\min(b, c) \le \min(b, d)$ 。故 $V_{post} \ge V_{pre}$ 。

情況二：

c < a

此時 $c < a \le b$ ，故 $\min(b, c) = c$ ， $\min(a, c) = c$ 。

$V_{pre} = \min(a, d) \times c$
$V_{post} = c \times \min(b, d)$

因為 $a \le b$ ，所以 $\min(a, d) \le \min(b, d)$ 。故 $V_{post} \ge V_{pre}$ 。

綜上，將逆序對交換成同序後，乘積不會變小。反覆交換直到兩陣列同序即得最優解。

二分搜尋維護動態更新

由於題目涉及 $q$ 次單點增加（每次 $+1$ ），我們不能每次重新排序（ $O(n \log n)$ 太慢）。需要在 $O(\log n)$ 時間內維護排序陣列和答案。

當原陣列 $A_i$ 的值 $v$ 增加 1 時，相當於將排序陣列 $C$ 中任意一個值為 $v$ 的位置變成 $v+1$ 。為了保持 $C$ 的有序性，我們選擇 $C$ 中最右邊的那個 $v$ 進行增加：

設 $idx$ 為 $C$ 中值為 $v$ 的最後一個元素位置
將 $C[idx]$ 從 $v$ 更新為 $v+1$
由於 $C[idx+1] \ge v+1$ （若存在），更新後 $C[idx] \le C[idx+1]$ ，陣列依然有序

由於 $C$ 是有序的，使用二分搜尋即可在 $O(\log n)$ 內找到該位置。

利用模意義下的乘法反元素(逆元)更新乘積

我們維護當前的總乘積 $P$ 。更新 $C[idx]$ 時，只有當它是瓶頸時，乘積才會改變：

若 $C[idx] < D[idx]$ ：該位置對乘積的貢獻從 $C[idx]$ 變為 $C[idx] + 1$

P' = P \times \dfrac{(C[idx]+1)}{C[idx]}

若 $C[idx] \ge D[idx]$ ：該位置貢獻為 $D[idx]$ ，更新 $C[idx]$ 不影響最小值， $P$ 不變

模意義下的乘法反元素(逆元)計算

由於 $\text{MOD} = 998244353$ 是質數，根據費馬小定理：

a^{-1} \equiv a^{\text{MOD}-2} \pmod{\text{MOD}}

在 Python 中可以直接用 pow(B[x], -1, MOD) 計算。

這樣每次查詢只需 $O(\log n)$ （二分搜尋）+ $O(\log \text{MOD})$ （快速冪求乘法反元素）。

實現細節

維護兩個排序陣列 sl1（對應 $C$ ）和 sl2（對應 $D$ ）
同時保留原陣列 $A, B$ 以得知每次操作增加的具體數值
操作 $A_x$ 時：取 $v = A[x]$ ，找 bisect_right(sl1, v) - 1 作為更新點，判斷是否需更新 prod，然後將 sl1[idx] 和 A[x] 都加 1

複雜度分析

時間複雜度： $\mathcal{O}(n \log n + q \log n)$ $O (n lo g n + q lo g n)$
- 初始排序 $O(n \log n)$
- 每次查詢：二分搜尋 $O(\log n)$ ，乘法反元素 $O(\log \text{MOD})$
空間複雜度： $\mathcal{O}(n)$ ，用於存儲排序陣列

Code

from bisect import bisect_right

MOD = 998244353

def solve():
    n, q = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    assert len(A) == n and len(B) == n

    sl1 = sorted(A)
    sl2 = sorted(B)

    prod = 1
    for x, y in zip(sl1, sl2):
        prod = (prod * min(x, y)) % MOD
    ans = [prod]
    for _ in range(q):
        o, x = map(int, input().split())
        x -= 1
        if o == 1:
            idx = bisect_right(sl1, A[x]) - 1
            if sl1[idx] < sl2[idx]:
                prod = (prod * pow(A[x], MOD - 2, MOD)) % MOD
                prod = (prod * (A[x] + 1)) % MOD
            sl1[idx] += 1
            A[x] += 1
        else:
            idx = bisect_right(sl2, B[x]) - 1
            if sl2[idx] < sl1[idx]:
                prod = (prod * pow(B[x], -1, MOD)) % MOD
                prod = (prod * (B[x] + 1)) % MOD
            sl2[idx] += 1
            B[x] += 1
        ans.append(prod)
    print(*ans)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

PROMPT

這裡什麼都沒有。