Codeforces 398D Instant Messenger：平方根分解處理動態圖查詢

題目大意

動態無向圖，支持四種操作：

• O u：用戶 u 上線
• F u：用戶 u 下線
• A u v：添加邊 (u,v)
• D u v：刪除邊 (u,v)
• C u：查詢用戶 u 的在線好友數

n ≤ 50000，q ≤ 250000，邊無重複。要求離線處理所有操作。

核心洞見：度數分類 + 平方根分解

對於查詢 C u，需統計 u 的鄰居中在線數量。若逐條遍歷鄰居，最壞 O(deg(u)) 過慢。
觀察：若 deg(v) > deg(u)，則這類「大度鄰居」數量有限。
證明：設 deg(u)=d，大度鄰居數 x，則 d ≥ x 且圖中總度數和 ≥ x(x+1) ≤ 2E → x ≤ √(2E)。

數據結構設計

• deg[u]：節點最終度數（離線預處理得出）
• is_online[u]：當前在線狀態
• from_small[u]：鄰居中 度數 ≤ deg[u] 且在線的數量（實時維護）
• 查詢時：ans = from_small[u] + 遍歷大度鄰居統計在線數

操作處理

複雜度分析

• 預處理：O(E log E) 排序去重邊，計算度數。
• 每次操作：O(1) 或 O(√E)（遍歷大度鄰居）。
• 總體：O((E+Q)√E)，通過 E≤400000，Q≤250000。

關鍵代碼片段（C++）

// 維護 from_small
void modify_dot(int u, int st) { // st=1 上線, 0 下線
    is_online[u] = st;
    int dt = st ? 1 : -1;
    for (auto [v, eid] : G[u]) if (edge_active[eid])
        from_small[v] += dt;
}

int query_dot(int u) {
    int ans = from_small[u];
    for (auto [v, eid] : G[u]) if (edge_active[eid])
        ans += is_online[v]; // 只遍歷大度鄰居（構建時已過濾）
    return ans;
}

完整代碼見原文，包含離線讀取所有操作、構建最終圖、預計算度數、構建 G[u] 僅存儲 deg[v] ≥ deg[u] 的鄰居（即大度鄰居），從而保證查詢遍歷量 ≤ √E。

總結

本題是離線 + 度數分類 + 平方根分解的教科書級應用。關鍵技巧：

1. 離線獲取最終度數，作為分類標準（不隨動態變化）。
2. 維護「小度鄰居在線數」from_small，查詢時只需掃描「大度鄰居」。
3. 大度鄰居數量有界於 √(2E)，保證查詢效率。

此模式廣泛適用於動態圖的「點查詢鄰居屬性聚合」問題。