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

🔗 CF2053B Outstanding Impressionist

Problem Statement

題目簡述

給定 $n$ 個區間 $[l_i, r_i]$ ，每個區間 $i$ 需選一個整數 $w_i \in [l_i, r_i]$ 。
對於每個 $i$ ，判斷是否存在一種選法，使得 $w_i$ 與所有其他 $w_j$ ( $j \ne i$ ) 都不同。
若存在，輸出 1；否則輸出 0。

Constraints

約束條件

$1 \leq n \leq 2 \cdot 10^5$
$1 \leq l_i \leq r_i \leq 2n$

思路：前綴和 (Prefix Sum)

關鍵觀察

如果區間 $[l_i, r_i]$ 滿足 $l_i = r_i$ ，則 $w_i$ 必須取值 $l_i$ ，我們稱此為「固定區間」。
固定區間強佔了它所指向的數值，其他區間若想不與它衝突，就必須避開這個值。

判斷唯一性

設 $\text{cnt}[v]$ 為數值 $v$ 被固定區間覆蓋的次數。

情況 1：固定區間 (

l_i = r_i

)

$w_i$ 必定為 $l_i$ 。只有在沒有其他區間也被迫取 $l_i$ ，即 $\text{cnt}[l_i] == 1$ 時， $i$ 才是唯一的。

情況 2：非固定區間 (

l_i < r_i

)

$w_i$ 可在 $[l_i, r_i]$ 中任選。只要 $\exists\, v \in [l_i, r_i]$ 使得 $\text{cnt}[v] = 0$ ，就能讓 $w_i = v$ ，且其他非固定區間都能避開 $v$ 。

前綴和優化

為了快速查詢「區間 $[l, r]$ 內是否有空位」，我們建立前綴和陣列 $s$ ：

$s[x]$ ：數值 $0 \sim x$ 中，滿足 $\text{cnt}[v] = 0$ 的數量（即空位數量）。
查詢： $s[r] - s[l-1] > 0$ 表示有空位。

約束的利用

由於 $1 \le l_i \le r_i \le 2n$ ，所有數值都落在 $[1, 2n]$ 範圍內。
因此 $\text{cnt}$ 與 $s$ 陣列的大小僅需 $O(n)$ ，確保了整體複雜度為線性。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，遍歷區間並用前綴和 $O(1)$ 查詢。
空間複雜度： $\mathcal{O}(n)$ ，用於存儲 $\text{cnt}$ 與 $s$ 陣列（大小為 $2n+1$ ）。

Code

from itertools import accumulate

def solve():
    n = int(input())
    intervals = [tuple(map(int, input().split())) for _ in range(n)]
    assert len(intervals) == n
    
    cnt = [0] * (2 * n + 1)
    for l, r in intervals:
        cnt[l] += (l == r)
    s = list(accumulate(cnt, func=lambda x, y: x + (y == 0)))

    ans = []
    for l, r in intervals:
        if l == r:
            ans.append('1' if cnt[l] == 1 else '0')
        else:
            ans.append('1' if s[r] - s[l - 1] > 0 else '0')
    print(*ans, sep='')

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

寫在最後

PROMPT

這裡什麼都沒有。