UvaLive 6667 Longest Chain：分治 + 樹狀數組解三維偏序 LIS

UvaLive 6667 Longest Chain：CDQ 分治 + BIT 解三元組嚴格偏序最長鏈

問題描述

給定部分三元組 (x, y, z)，另一部分由隨機函數生成。求最長鏈長度，要求嚴格偏序：a.x > b.x 且 a.y > b.y 且 a.z > b.z。

核心挑戰

• 三維偏序 + 嚴格大於（非 ≥）
• 數據量大：需 O(N log²N) 算法
• x 相等時不能互相轉移，需特殊處理

CDQ 分治 + 樹狀數組方案

1. 排序： 按 x 升序、y 升序、z 升序
2. CDQ 分治： 以 x 為分治維度，遞歸解決左半部，再用左半部更新右半部
3. y 維度處理： 合併時按 y 排序，y 相等時原序號大的排前面，保證嚴格大於不互相更新
4. z 維度 BIT： 離散化 z 值，用樹狀數組維护前綴最大 dp 值
5. x 相等問題： 維護兩棵 BIT：
   • av：左半部所有點更新
   • bv：僅 x != mid+1.x 的點更新
   • 右半部點查詢時：若 x == mid+1.x 用 bv，否則用 av

關鍵代碼片段

bool cmp(int a, int b) {
    if (po[a].y != po[b].y) return po[a].y < po[b].y;
    return a > b;  // y 相等時序號大的在前，防止同 y 互相更新
}

void solve(int l, int r) {
    if (l == r) { ans = max(ans, dp[l]); sz[l] = po[l].z; return; }
    int mid = (l+r)>>1;
    // 分治左半部
    // 合併排序 y
    solve(l, mid);
    // 初始化 BIT
    // 左半部更新 BIT (av/bv)
    // 右半部查詢 BIT 更新 dp
    solve(mid+1, r);
    // 合併 z 有序
}

隨機數生成器

int A, B, C = ~(1<<31), M = (1<<16)-1;
int rd() {
    A = 36969 * (A & M) + (A >> 16);
    B = 18000 * (B & M) + (B >> 16);
    return (C & ((A << 16) + B)) % 1000000;
}

複雜度

O(N log²N)，N ≤ 300,000 可在時限內通過。