題目來源：HDU 1540 / POJ Monthly
核心標籤：線段樹、區間合併、堆疊模擬回滾
有 n 個村莊排成一線，初始全連通。支援三種操作：
D x：摧毀第 x 個村莊（斷開連接）Q x：查詢包含第 x 村莊的最大連通區間長度R：恢復最近一次被摧毀的村莊（後進先出）n, m ≤ 50,000，需單點更新、區間查詢、歷史回滾，均攤 O(log n)。
每個節點維護三個關鍵值：
ls：以該區間左端點為起點的最大連續連通長度rs：以該區間右端點為終點的最大連續連通長度ms：該區間內部的最大連續連通長度葉子節點初始 ls = rs = ms = 1（連通），摧毀後歸零。
void push_up(int num) {
// 左區間
t[num].ls = t[num<<1].ls;
if (t[num<<1].ls == t[num<<1].r - t[num<<1].l + 1) // 左子樹全滿
t[num].ls += t[num<<1|1].ls;
// 右區間
t[num].rs = t[num<<1|1].rs;
if (t[num<<1|1].rs == t[num<<1|1].r - t[num<<1|1].l + 1) // 右子樹全滿
t[num].rs += t[num<<1].rs;
// 內部最大 = max(左子樹最大, 右子樹最大, 跨中間合併)
t[num].ms = max({t[num<<1].ms, t[num<<1|1].ms, t[num<<1].rs + t[num<<1|1].ls});
}
int query(int x, int num) {
if (t[num].l == t[num].r || t[num].ms == 0 || t[num].ms == t[num].r - t[num].l + 1)
return t[num].ms; // 葉子/全空/全滿 直接返回
int mid = (t[num].l + t[num].r) >> 1;
if (x <= mid) {
// x 在左子樹，若落在左子樹的右連通段，需合併右子樹左段
if (x >= t[num<<1].r - t[num<<1].rs + 1)
return query(x, num<<1) + query(mid+1, num<<1|1);
else
return query(x, num<<1);
} else {
// x 在右子樹，對稱處理
if (x <= t[num<<1|1].l + t[num<<1|1].ls - 1)
return query(x, num<<1|1) + query(mid, num<<1);
else
return query(x, num<<1|1);
}
}
用陣列 s[MAXN] 模擬堆疊，D x 時 s[top++] = x，R 時 x = s[--top] 再 update(x, 1) 恢復。完美契合「最近一次」的 LIFO 語義。
O(n)，單次更新/查詢 O(log n)，總 O((n+m) log n)4n 節點，堆疊 mpush_up 邊界條件、查詢時跨中間合併邏輯、char ch[2] 讀指令防 RE此題是線段樹「區間合併」與「歷史版本」雙重考點的教科書級範例，掌握後可舉一反三解決類似「動態連通性 + 回滾」問題。
