AtCoder 🌈 AWC0022C Road Pothole Survey

🔗 AWC0022C Road Pothole Survey

Problem Statement

題目簡述

有 $N$ 塊磁磚排成一列，其中 $M$ 塊已損壞。
$K$ 輛車分別行經連續區段 $[L_i, R_i]$，若該區段內損壞磁磚數量 $\geq T$，則報告為「需要維修」。> 對每輛車輸出判定結果。

Constraints

約束條件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq N$，$1 \leq K \leq 2 \times 10^5$，$1 \leq T \leq N$
• $1 \leq B_i \leq N$，所有 $B_i$ 互不相同
• $1 \leq L_i \leq R_i \leq N$

---

思路：前綴和

典型的區間計數問題，用前綴和即可 $O(1)$ 回答每筆查詢。

建立長度為 $N$ 的 0/1 陣列 A，損壞的位置標記為 1，再對 A 做前綴和得到 s。對於查詢 $[L, R]$，損壞磁磚數量為 $s[R] - s[L-1]$，與閾值 $T$ 比較即可。

複雜度分析

• 時間複雜度：$\mathcal{O}(N + M + K)$
• 空間複雜度：$\mathcal{O}(N)$

Code

from itertools import accumulate


def solve():
    N, M, K, T = map(int, input().split())
    B = list(map(int, input().split()))

    A = [0] * N
    for b in B:
        A[b - 1] = 1
    s = list(accumulate(A, initial=0))

    ans = []
    for _ in range(K):
        L, R = map(int, input().split())
        ans.append("YES" if s[R] - s[L - 1] >= T else "NO")
    print(*ans, sep="\n")


if __name__ == "__main__":
    solve()