HDU 4973 線段樹維護區間翻倍與最大頻次查詢

HDU 4973 線段樹維護區間翻倍與最大頻次查詢

初始隊列為 1, 2, ..., n。操作 D l r 將區間 [l, r] 內每個元素複製一份（長度翻倍）；操作 Q l r 查詢區間 [l, r] 內出現次數最多的數字的個數。n, m ≤ 50000，區間長度可達 1e8，需用線段樹隱式維護。

線段樹節點信息

• num：該節點覆蓋的總元素個數。
• Max：該區間內任意單一數字的最大出現次數。

核心操作

Build

遞歸建樹，葉子節點 num = Max = 1，內部節點 num = 左.num + 右.num，Max = max(左.Max, 右.Max)。

Update（區間翻倍）

將 [L, R] 映射到當前節點的相對位置 [ll, rr]。若完全落在左/右子樹，遞歸更新；跨越中點則拆分為兩段分別更新。更新後 PushUp 合併信息。

Query（最大頻次）

若查詢區間完全覆蓋當前節點，直接返回 Max；否則按相對位置遞歸左右子樹，取最大值。

關鍵代碼

void Update(int l, int r, LL ll, LL rr, int site) {
    if (l == r) { num[site] += rr - ll + 1; Max[site] = num[site]; return; }
    LL tmp = num[site<<1]; int mid = (l+r)>>1;
    if (rr <= tmp) Update(l, mid, ll, rr, site<<1);
    else if (ll > tmp) Update(mid+1, r, ll-tmp, rr-tmp, site<<1|1);
    else { Update(l, mid, ll, tmp, site<<1); Update(mid+1, r, 1, rr-tmp, site<<1|1); }
    PushUp(site);
}

複雜度

• 建樹：O(n)
• 單次操作：O(log n)
• 總體：O((n + m) log n)，滿足限制。

本題展示了線段樹處理「隱式數組擴展」與「區間統計」的強大能力，是線段樹進階應用的優秀範例。