您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

Codeforces 500E New Year Domino：倍增與線段樹離線解法

編輯：關於C++

問題描述

有 n 個多米諾骨牌按 x 座標遞增排列，第 i 個位於 x=p_i，長度為 l_i。推倒第 x_j 個骨牌，它會向右倒下，觸碰到的骨牌也會連鎖倒下。有 q 個查詢：推倒第 x 個骨牌，希望第 y 個骨牌也倒下。可以花費 1 元增加任意骨牌長度 1。每個查詢獨立，求最小花費。

解法一：離線 + 線段樹

觀察骨牌倒下的傳播：第 i 個骨牌倒下能觸及的最右位置為 reach[i] = p_i + l_i。若 reach[i] >= p_{i+1}，則會觸發下一個。實際上，倒下過程形成一個「覆蓋區間」的合併。對於查詢 (x, y)，我們需要知道從 x 開始，經過連鎖後能否覆蓋到 p_y。若不能，需補齊的長度即為 p_y 與實際覆蓋右端點的差值（扣除中間已覆蓋的長度）。

離線處理：按查詢的左端點 x 從大到小排序，維護一個線段樹記錄已加入骨牌的覆蓋區間長度。逐個加入骨牌，更新線段樹；回答查詢時，查詢區間 [x, y-1] 的已覆蓋總長度，答案 = p_y - p_x - coveredLen。

解法二：倍增（Binary Lifting）

預處理每個骨牌向右「跳躍」的下一個未被覆蓋的骨牌及所需補齊長度。定義 nxt[i][k] 為從 i 經過 2^k 次跳躍到達的骨牌索引，cost[i][k] 為累積補齊長度。利用單調棧從右向左維護每個骨牌直接觸發的下一個骨牌。查詢時，從 x 開始，按二進制分解跳躍直到超過 y，累加 cost 即為答案。

代碼實現（倍增版）

#include 
using namespace std;
const int MAXN = 200200;
const int LOG = 20;
int n, p[MAXN], l[MAXN];
int nxt[MAXN][LOG];
long long cost[MAXN][LOG];
int stk[MAXN], top;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &p[i], &l[i]);
    // 單調棧求直接觸發的下一個骨牌
    for (int i = n; i >= 1; --i) {
        while (top && p[stk[top]] + l[stk[top]] <= p[i] + l[i]) --top;
        nxt[i][0] = stk[top];
        if (p[i] + l[i] >= p[stk[top]]) cost[i][0] = 0;
        else cost[i][0] = p[stk[top]] - p[i] - l[i];
        stk[++top] = i;
    }
    // 倍增預處理
    for (int k = 1; k < LOG; ++k) {
        for (int i = 1; i <= n; ++i) {
            nxt[i][k] = nxt[nxt[i][k-1]][k-1];
            cost[i][k] = cost[i][k-1] + cost[nxt[i][k-1]][k-1];
        }
    }
    int q; scanf("%d", &q);
    while (q--) {
        int x, y; scanf("%d%d", &x, &y);
        long long ans = 0;
        for (int k = LOG-1; k >= 0; --k) {
            if (nxt[x][k] <= y) {
                ans += cost[x][k];
                x = nxt[x][k];
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}