Luogu 🟢 P1314 [NOIP 2011 提高组] 聪明的质监员

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

🔗 P1314 [NOIP 2011 提高组] 聪明的质监员

Problem Statement

題目簡述

給定 $n$ 個礦石（每個有重量與價值）以及 $m$ 個區間。

選一個門檻 $W$，對每個區間把「重量 $\ge W$」的礦石挑出來，令該區間的檢驗值為「挑出數量」乘以「挑出價值總和」，再把所有區間的檢驗值加總得到總檢驗結果 $y$。

求能讓 $|s-y|$ 最小的值。

Constraints

約束條件

• $1 \le n,m \le 2\times 10^5$
• $0 < w_i, v_i \le 10^6$
• $0 < s \le 10^{12}$
• $1 \le l_i \le r_i \le n$

---

思路：二分答案 + 區間前綴和

先把題目「固定 $W$ 時如何算 $y$」與「要找最接近 $s$ 的 $W$」拆開。

固定門檻 $W$：如何快速算總檢驗結果 $y(W)$

對於一個區間，檢驗值是：

$$\text{(符合者數量)} \times \text{(符合者價值總和)}$$

因此在掃描礦石時，我們只關心「重量是否至少為 $W$」。把每個位置轉成兩個序列：

• 指示序列：符合則是 $1$，否則 $0$
• 價值序列：符合則是價值，否則 $0$

對這兩個序列各做一次前綴和，就能在 $\mathcal{O}(1)$ 取出任意區間的「符合者數量」與「符合者價值總和」，再相乘並累加所有區間，得到 $y(W)$。

為什麼只要兩個前綴和就夠？

因為區間內檢驗值只依賴「兩個可加量」：符合者的個數與符合者價值和；它們都能用前綴和做區間查詢。

為什麼可以二分 $W$

當門檻 $W$ 變大時，符合「重量至少為 $W$」的礦石只會變少、不會變多。
因此每個區間的「符合者數量」與「符合者價值總和」都是隨 $W$ 非增，乘積也隨 $W$ 非增；總和 $y(W)$ 同樣是單調不增。

單調性意味著：

• 若某個 $W$ 使得 $y(W) \ge s$，那麼較小的門檻也會滿足 $\ge s$
• 若某個 $W$ 使得 $y(W) < s$，那麼較大的門檻也會滿足 $< s$

所以可以二分找「單調函數穿越 $s$ 的交界點」，再在交界兩側各取一次距離。

如何找出與 $s$ 最接近的檢驗結果

因為總檢驗值隨門檻上升而單調不增，最接近標準值的點一定出現在函數從大於等於 $s$ 跨越到小於 $s$ 的交界附近。

二分搜尋結束後，自然會得到兩個相鄰的候選門檻（可能相差 1，或落在邊界）。分別計算這兩個門檻對應的總檢驗值，取出與 $s$ 差值的較小者即可。

邊界與越界

若門檻超過所有礦石重量，則所有貢獻為 $0$；若門檻足夠小，則幾乎全選所有礦石。必須正確處理左右邊界情況，避免遺漏最小差值。

複雜度分析

• 時間複雜度：$\mathcal{O}\big((n+m)\log(\max w)\big)$
• 空間複雜度：$\mathcal{O}(n)$

---

Code

def solve():
    n, m, s = map(int, input().split())  # s 為標準檢驗值
    items = [tuple(map(int, input().split())) for _ in range(n)]
    queries = [tuple(map(int, input().split())) for _ in range(m)]

    s_cnt = [0] * (n + 1)
    s_sum = [0] * (n + 1)

    def check(W):
        """固定門檻 W 時計算總檢驗值 y"""
        for i, (w, v) in enumerate(items, start=1):
            s_cnt[i] = s_cnt[i - 1] + (1 if w >= W else 0)
            s_sum[i] = s_sum[i - 1] + (v if w >= W else 0)
        res = 0
        for l, r in queries:
            res += (s_cnt[r] - s_cnt[l - 1]) * (s_sum[r] - s_sum[l - 1])
        return res

    maxW = max(w for w, _ in items)
    left, right = 0, maxW
    while left <= right:
        mid = (left + right) // 2
        if check(mid) >= s:  # y >= s 時提高門檻以降低總檢驗值
            left = mid + 1
        else:
            right = mid - 1

    # 檢查二分收斂後的兩個候選門檻，取與 s 差值的最小值
    print(min(s - check(left), check(right) - s))


if __name__ == "__main__":
    solve()