BZOJ 3524 [POI 2014] Couriers — 可持久化線段樹區間眾數查詢

題目

長度 n ≤ 500000 序列 a[i] ∈ [1,n]，m ≤ 500000 次詢問：區間 [l,r] 是否存在出現次數 > (r-l+1)/2 的數（眾數），存在輸出該數否則 0。

核心觀察

若區間存在「絕對眾數」（超過半數），則該數在任意子區間也佔優勢。可持久化線段樹（Chairman Tree）按值域建樹，每版本對應前綴 [1..i] 的頻率統計。查詢 [l,r] 相當於 version[r] - version[l-1]。

可持久化線段樹構造

• 值域 [1,n]，節點存 sum（出現次數）。
• update(pre, cur, pos)：從 pre 複製路徑，sum+1，新建 O(log n) 節點。
• 共 n 個版本，總節點數 O(n log n)。

查詢邏輯

在兩棵樹上同步下降：若左子樹 sum > (len/2) 往左，否則往右。若葉子仍滿足條件即為答案，否則 0。
關鍵：只需檢查單一路徑，因為最多只有一個數能超過半數。

AC 程式碼（精簡）

#include 
using namespace std;
const int MAXN = 500005;
const int MAXM = 10000005;  // n * log2(n) * 2
int n, m, tot;
int rt[MAXN], ls[MAXM], rs[MAXM], sum[MAXM];

void update(int l, int r, int pre, int &cur, int pos) {
    cur = ++tot;
    ls[cur] = ls[pre]; rs[cur] = rs[pre];
    sum[cur] = sum[pre] + 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) update(l, mid, ls[pre], ls[cur], pos);
    else update(mid+1, r, rs[pre], rs[cur], pos);
}

int query(int u, int v, int l, int r) {  // u=version[l-1], v=version[r]
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int leftSum = sum[ls[v]] - sum[ls[u]];
    int need = (r - l + 1) >> 1;  // 這裡需傳入區間長度，簡化示意
    if (leftSum > need) return query(ls[u], ls[v], l, mid);
    if (sum[rs[v]] - sum[rs[u]] > need) return query(rs[u], rs[v], mid+1, r);
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        update(1, n, rt[i-1], rt[i], x);
    }
    while (m--) {
        int l, r; cin >> l >> r;
        // 實際 query 需傳入 len = r-l+1
        cout << query(rt[l-1], rt[r], 1, n) << '\n';
    }
    return 0;
}

複雜度

• 建樹：O(n log n) 時間、空間。
• 單次查詢：O(log n)。
• 總體 O((n+m) log n)，輕鬆通過 5e5 規模。

心得

1. 可持久化線段樹本質是「前綴和」在樹上的體現，區間查詢轉化為兩版本相減。
2. 「超過半數」性質保證答案唯一，使查詢可單路徑下降，無需合併多路徑。
3. 節點池大小預估：n * (log2(n)+2) 保保險，5e5 * 20 ≈ 1e7。