UVA Live 4730 Kingdom：並查集 + 線段樹動態維護城市群統計

問題建模

平面上 N 個城市，坐標 (x,y)。操作：
1. road a b：在城市 a,b 間建路（連通）。
2. line y C：查詢直線 y = C 上有多少個城市群（連通塊）、總共多少城市。
城市群定義：通過道路直接或間接相連的城市集合。

核心洞察

• 道路建設只有合並操作 → **並查集** 維護連通塊。
• 查詢關注 y 坐標 → 將 y 軸離散化，用**線段樹**維護每個 y 坐標上的城市群數與城市數。

數據結構設計

• 並查集：fa[]、sz[]（城市數）、minY[]、maxY[]（y 坐標極值）。
• 線段樹：每個節點存 cnt（城市群數）、sum（城市總數），支持區間加減、單點查詢。

合並邏輯

void unite(int a, int b) {
    a = find(a); b = find(b); if (a==b) return;
    // 從線段樹移除兩個舊連通塊的貢獻
    if (minY[a] != maxY[a]) update(minY[a]+1, maxY[a], -1, -sz[a]);
    if (minY[b] != maxY[b]) update(minY[b]+1, maxY[b], -1, -sz[b]);
    // 合並
    fa[b] = a; sz[a] += sz[b];
    minY[a] = min(minY[a], minY[b]);
    maxY[a] = max(maxY[a], maxY[b]);
    // 加入新連通塊貢獻
    if (minY[a] != maxY[a]) update(minY[a]+1, maxY[a], +1, +sz[a]);
}

查詢處理

line y C → 查詢線段樹位置 C+1（離散化後）的 cnt 和 sum。

坐標離散化

y 坐標範圍 [0, 1e6]，線段樹直接建在 [1, 1e6+1] 上，無需額外離散化，內存 4e6 節點可接受。

複雜度

並查集 O(α(N))，線段樹 O(log MAXY)，總 O((N+M) log MAXY)，N≤1e5, M≤2e5 極快。