🔗 🔵 ABC389F Rated Range

Problem Statement

題目簡述

有 $N$ 場比賽。在第 $i$ 場比賽中，若選手的 rating 落在 $[L_i, R_i]$ 內，則 rating 加一。給定 $Q$ 筆查詢，每筆查詢給初始 rating $X$ ，求參加完所有 $N$ 場比賽後的最終 rating。

Constraints

約束條件

$1 \leq N \leq 2 \times 10^5$
$1 \leq L_i \leq R_i \leq 5 \times 10^5$
$1 \leq Q \leq 3 \times 10^5$
$1 \leq X \leq 5 \times 10^5$
所有輸入均為整數

思路：線段樹 + 二分搜尋

題型定位

這是一道「區間加法 + 單調性維護」的題目。核心觀察是：同時模擬所有初始分數的變化過程，可以發現分數映射始終保持單調不減，從而用二分定位每次操作影響的區間，再用線段樹做區間加法。

暴力做法

最直接的想法：對每個查詢 $X$ ，模擬 $N$ 場比賽。每場比賽檢查當前分數是否在 $[L_i, R_i]$ 內，若是則加一。時間複雜度 $O(NQ)$ ，在 $N, Q \le 2 \times 10^5$ 下不可行。

反轉視角

瓶頸在於對每個查詢獨立模擬。換個角度：同時考慮所有可能的初始分數。

令 $f(j)$ 表示初始分數為 $j$ 的選手，參加完所有比賽後的最終分數。初始時 $f(j) = j$ 。每場比賽 $[L, R]$ 的作用是：將所有滿足 $L \le f(j) \le R$ 的 $j$ 對應的分數加一。

問題變為：維護一個長度為值域的陣列，支援：

找到滿足 $L \le f(j) \le R$ 的 $j$ 的範圍
對該範圍內的所有 $f(j)$ 加一
對每個查詢輸出 $f(X)$

單調性

單調性證明

初始時 $f(j) = j$ ，顯然單調不減。每次操作將一段區間的值加一，最多只會讓某個位置的值追上後面一個位置，不會破壞單調不減的性質。因此任意時刻 $f$ 都是單調不減的。

因為 $f$ 單調不減，可以用二分搜尋定位區間邊界：

找到最小的 $j$ 使得 $f(j) \ge L$ → 這是區間的左端點
找到最小的 $j$ 使得 $f(j) > R$ → 這是區間的右端點（不包含）

二分細節

AtCoder Library 的 max_right(l, cond) 會從 $l$ 出發，找到第一個不滿足 cond 的位置。因此：

找第一個 $\ge L$ 的位置：條件設為 < L，max_right 會停在第一個 $\ge L$ 處
找第一個 $> R$ 的位置：條件設為 $\le R$ ，max_right 會停在第一個 $> R$ 處

注意這裡的區間是左閉右開 $[l, r)$ 。

線段樹維護

確定區間 $[l, r)$ 後，就是一個區間加法的操作。需要區間更新 + 單點查詢，使用懶標記線段樹。這裡直接使用 AtCoder Library 的 LazySegTree：

值的合併：取最大值（因為單調性，取 max 就等於取區間內任意值）
懶標記：加法，composition 是加法疊加
初始值： $v = [0, 1, 2, \dots, MX-1]$

核心套路

這題可遷移的模式是：維護一個單調不減的映射，用二分定位操作區間，再用線段樹做批量更新。遇到「對一個區間內的元素做相同操作」且「元素間的相對順序不變」的問題時，都可以考慮這個思路。

複雜度分析

時間複雜度： $\mathcal{O}(X + N \log X + Q \log X)$ $O (X + N lo g X + Q lo g X)$
- 初始化線段樹： $\mathcal{O}(X)$ ，其中 $X$ 為值域大小
- 每場比賽：二分定位 $\mathcal{O}(\log X)$ ，區間更新 $\mathcal{O}(\log X)$
- 每次查詢： $\mathcal{O}(\log X)$
空間複雜度： $\mathcal{O}(X)$ （線段樹）

Code

from atcoder.lazysegtree import LazySegTree

N = int(input())
contests = [tuple(map(int, input().split())) for _ in range(N)]
Q = int(input())
queries = [int(input()) for _ in range(Q)]

MX = max(max(r for _, r in contests), max(q for q in queries)) + 1
lst = LazySegTree(op=max,
                  e=0,
                  mapping=lambda f, x: f + x,
                  composition=lambda f, g: f + g,
                  id_=0,
                  v=list(range(MX)))

for l, r in contests:
    # 找到最小的 j 使得 f(j) >= l
    l = lst.max_right(0, lambda x: x < l)
    # 找到最小的 j 使得 f(j) > r，即第一個不滿足 <= r 的位置
    r = lst.max_right(0, lambda x: x <= r)
    lst.apply(l, r, 1)

for q in queries:
    print(lst.get(q))