BZOJ 2957 樓房重建：分塊與線段樹雙解法

題目大意

n 棟樓初始高度 0。每次修改某棟樓高度，查詢從原點 (0,0) 看去能看到多少棟樓（即斜率單調遞增的樓數）。n, m ≤ 10^5。

解法一：分塊 (Sqrt Decomposition)

• 分塊大小 S ≈ √(n log n)，共 L 塊。
• 每塊維護斜率單調遞增的凸包序列（即該塊內從左到右能看到的樓）。
• 修改：暴力重建所在塊的凸包，O(S)。
• 查詢：遍歷所有塊，在每塊凸包上二分查找第一個斜率大於當前最大斜率的樓，累加可見數，更新最大斜率。O(L log S)。
• 總體：O(m (S + L log S))，取 S = √(n log n) 達到最優。

解法二：線段樹

• 節點維護：`mx` = 區間最大斜率，`cnt` = 區間內可見樓數（假設從左邊看進來，初始斜率為 0）。
• 合併：`cnt = left.cnt + right.query(left.mx)`，其中 `query(x)` 返回右區間在初始斜率 x 下可見樓數。
• 查詢 `query(x)`：若 `left.mx ≤ x` 直接進右子樹；否則遞歸左子樹並加上右子樹相對左子樹最大斜率的增量。利用線段樹結構實現 O(log² n) 單次修改查詢。

線段樹核心代碼 (C++)

struct SegTree {
    double mx[N<<2];
    int cnt[N<<2];
    
    // 計算右子樹在給定初始斜率 x 下的可見增量
    int calc(int rt, int l, int r, double x) {
        if (l == r) return mx[rt] > x;
        int mid = (l+r)>>1;
        if (mx[ls] <= x) return calc(rs, mid+1, r, x);
        else return cnt[rt] - cnt[ls] + calc(ls, l, mid, x);
    }
    
    void pushup(int rt) {
        mx[rt] = max(mx[ls], mx[rs]);
        cnt[rt] = cnt[ls] + calc(rs, mid+1, r, mx[ls]);
    }
    
    void update(int rt, int l, int r, int pos, double val) {
        if (l == r) { mx[rt] = val; cnt[rt] = 1; return; }
        int mid = (l+r)>>1;
        if (pos <= mid) update(ls, l, mid, pos, val);
        else update(rs, mid+1, r, pos, val);
        pushup(rt);
    }
};

複雜度對比

線段樹常數較大但理論更優，分塊代碼簡單實際常快。