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

🔗 🟡 ABC434C Flapping Takahashi

Problem Statement

題目簡述

高橋在時刻 $0$ 處於高度 $H$ ，之後飛行 $10^9$ 秒。每秒高度變化量的絕對值 $\leq 1$ ，且高度必須始終 $> 0$ 。
給定 $N$ 個目標：在時刻 $t_i$ ，高度須在 $[l_i,\, u_i]$ 之間。問是否能同時滿足所有目標。

Constraints

約束條件

$1 \leq N \leq 10^5$
$1 \leq H \leq 10^9$
$1 \leq t_1 < t_2 < \dots < t_N \leq 10^9$
$1 \leq l_i \leq u_i \leq 10^9$
所有輸入為整數

思路：維護可能的區間

這是一道典型的動態維護可行區間的問題。

因為每一秒高橋高度的變化量在 $[-1, 1]$ 之間，在任意給定時刻，高橋所有可能達到的高度必然會構成一個連續的閉區間 $[L, R]$ 。我們可以依時間順序，漸進推導並更新這個區間。

初始狀態下，時間 $t_{\text{prev}} = 0$ ，初始高度為 $H$ ，因此起始區間為 $[H, H]$ 。

1. 區間的自然延展

假設從上一個時刻 $t_{\text{prev}}$ 來到目前的目標時刻 $t_i$ ，經過的時間 $\Delta t = t_i - t_{\text{prev}}$ 。
在這 $\Delta t$ 秒之內，可以達到的最低可能高度最多下降 $\Delta t$ ，最高可能高度最多上升 $\Delta t$ 。因此，原區間會自然展開為 $[L - \Delta t, R + \Delta t]$ 。

高度下界限制

題目要求「飛行過程中高度必須始終 $> 0$ 」。因此，即使展開後的理論下界 $L - \Delta t$ 小於等於 $0$ ，高橋也可以在過程中調整高度使其維持在 $1$ 及以上。
所以推導至當前時刻的預期合法區間 $[L', R']$ 為：

$L' = \max(L - \Delta t, 1)$
$R' = R + \Delta t$

2. 滿足當前目標需求

到達時刻 $t_i$ 時，題目額外限制了高度必須位於 $[l_i, u_i]$ 。這意味著高橋實際能處於的高度，必須同時滿足「預期可達到的範圍 $[L', R']$ 」與「目標範圍 $[l_i, u_i]$ 」。
也就是說，我們需要對這兩個區間取交集。

交集與更新

無解判定：如果目標區間與預期區間沒有重疊（也就是 $l_i > R'$ 或是 $u_i < L'$ ），代表高橋無法在此刻抵達目標範圍內的任何一點，直接輸出 No。
狀態更新：如果存在重疊，則將當前維護的區間更新為兩者的交集：
- $L = \max(L', l_i)$
- $R = \min(R', u_i)$

我們只需依序處理每一個目標點，且過程中推斷出交集區域都不為空集合，即代表一定存在至少一條連續合法的飛行路線，最後輸出 Yes。

複雜度分析

時間複雜度： $\mathcal{O}(N)$ （每個測資線性掃描所有目標）
空間複雜度： $\mathcal{O}(N)$ （儲存目標列表，不考慮儲存輸入的話可優化為常數空間）

Code

def solve():
    N, H = map(int, input().split())
    limits = [tuple(map(int, input().split())) for _ in range(N)]

    pt = 0
    L = R = H
    for t, l, r in limits:
        d = t - pt
        L = max(L - d, 1)  # 展開下界，截斷為 >= 1（高度 > 0）
        R = R + d  # 展開上界
        if l > R or r < L:  # 交集為空 → 無解
            print("No")
            return
        L = max(L, l)  # 與目標下界取交集
        R = min(R, r)  # 與目標上界取交集
        pt = t
    print("Yes")


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

寫在最後

Cover Image Credit

The cover image was created by @floomf. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.