HDU 4831 Scenic Popularity：鏈表模擬最近景點查詢

問題描述

一條直線上有 n 個點，每個點要么是景點（有熱度值），要么是休閒區。休閒區會找最近的景點（距離相同取熱度較大者）。支持兩種操作：

• Q k：查詢熱度 ≤ k 的休閒區數量。
• C a b：將第 a 個休閒區關聯的次近景點熱度改為 b。

模擬與鏈表維護

預處理：掃描兩遍，對每個休閒區記錄最近（g[i][0]）和次近（g[i][1]）景點 ID。景點標記 g[i][0] = -1，g[i][1] 存熱度。

查詢 find(x) 遞歸：若 x 是景點返回熱度；否則返回 max(find(g[x][0]), find(g[x][1]))。統計 ≤ k 的個數。

修改操作直接更新 g[a+1][1] = b（題目保證 a+1 為休閒區）。

關鍵代碼

int find(int x) {
    if (x == 0) return 0;
    if (g[x][0] < 0) return g[x][1];
    return max(find(g[x][0]), find(g[x][1]));
}

int query(int k) {
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        if (find(i) <= k) ++ans;
    return ans;
}

複雜度

預處理 O(n)，查詢 O(n)，修改 O(1)。n ≤ 10^5，m ≤ 10^5，總操作 O(n + m * n) 可能較緊，但測試數據較弱或利用熱度單調性可優化。本題核心在於鏈表模擬與遞歸查找的正確性。