題意#
題目給定一條長度為 \( x \) 的街道，初始無紅綠燈。
接著依序在不同位置新增 \( n \) 個紅綠燈，每次新增會切斷原有路段。
我們需要每次新增紅綠燈後，求出當下最長的無紅綠燈連續路段長度。
思路#
這是一個典型的動態區間問題。
需在序列中快速插入新節點，並更新區間長度的最大值。
在 C++ 中，可以搭配兩種資料結構實作：
set：記錄所有紅綠燈位置（包含起點 \( 0 \) 與終點 \( x \)）。multiset：存放所有路段長度（允許長度重複）。
新增紅綠燈位置 \( k \) 時，透過 upper_bound 找出其前後相鄰的紅綠燈。
新紅綠燈會切斷原有區間，因此需要從長度 multiset 中刪除舊的區間長度，
並加入切分後的兩段新長度。
更新完成後，最長路段即為 multiset 的最大元素（尾端）。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int x, n; cin >> x >> n;
// st 儲存紅綠燈位置，dis 儲存路段長度
set<int> st; multiset<int> dis;
// 初始化，前後各放一個紅綠燈，初始路段為整條街長
dis.insert(x); st.insert(0); st.insert(x);
for (; n--;) {
int k; cin >> k;
// 在紅綠燈位置中，找到第一個大於 k 的位置（右側的紅綠燈）
auto it = st.upper_bound(k);
// 取出這段路的長度，並從 dis 裡刪除單個元素
dis.erase(dis.find(*it-*(prev(it))));
// 將被切斷的兩段新路段長度加入 dis 中
dis.insert(k-*prev(it));
dis.insert(*it-k);
// 將新的紅綠燈位置加入 st 裡面
st.insert(k);
// 最長路段位於 dis 尾端
cout << *prev(dis.end()) << '\n';
}
}
