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

HDU 4267 區間加等差數列與單點查詢：線段樹深度解析

編輯：C++ 入門

題目核心挑戰

操作 1：在區間 [a, b] 內，對滿足 (i - a) % k == 0 的位置 i 加上 c（k ≤ 10）
操作 2：查詢單點 A[a] 的值
N, Q ≤ 50000，暴力 O(NQ) 必超時

關鍵洞察：將「等差步長」轉化為線段樹節點屬性

觀察發現：k 只有 1~10 共 10 種可能。在線段樹每個節點維護 k[11] 陣列，其中 k[d] 表示「以步長 d 為周期的懶標記增量」。

難點：右子樹區間左端點對齊問題

當更新區間 [L, R] 遞歸到右子樹 [mid+1, R] 時，原區間左端點 L 不再是子區間左端點。必須調整新左端點 tl 使 (tl - L) % k == 0：

int tl = mid + 1 + (k - (mid + 1 - L) % k) % k;
if (tl <= r) update(tl, r, 2*node+1, k, c);

完整線段樹實現

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 50010;

struct Node {
    int l, r;
    int k[12]; // k[1]~k[10] 存儲不同步長的懶標記
} tree[4 * MAXN];

int val[MAXN], N, Q;

void build(int l, int r, int idx) {
    tree[idx].l = l; tree[idx].r = r;
    memset(tree[idx].k, 0, sizeof(tree[idx].k));
    if (l != r) {
        int mid = (l + r) >> 1;
        build(l, mid, idx << 1);
        build(mid + 1, r, idx << 1 | 1);
    }
}

// 區間更新：在 [L, R] 中，步長為 step，每步加 inc
void update(int L, int R, int idx, int step, int inc) {
    if (L <= tree[idx].l && tree[idx].r <= R) {
        tree[idx].k[step] += inc;
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    if (R <= mid) update(L, R, idx << 1, step, inc);
    else if (L > mid) update(L, R, idx << 1 | 1, step, inc);
    else {
        update(L, mid, idx << 1, step, inc);
        int tl = mid + 1 + (step - (mid + 1 - L) % step) % step;
        if (tl <= R) update(tl, R, idx << 1 | 1, step, inc);
    }
}

// 查詢單點：累加路徑上所有節點對該點的貢獻
int query(int pos, int idx) {
    int ans = 0;
    for (int d = 1; d <= 10; d++)
        if ((pos - tree[idx].l) % d == 0)
            ans += tree[idx].k[d];
    
    if (tree[idx].l == tree[idx].r) return ans;
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    if (pos <= mid) return ans + query(pos, idx << 1);
    else return ans + query(pos, idx << 1 | 1);
}

int main() {
    while (~scanf("%d", &N)) {
        for (int i = 1; i <= N; i++) scanf("%d", &val[i]);
        build(1, N, 1);
        scanf("%d", &Q);
        while (Q--) {
            int op; scanf("%d", &op);
            if (op == 1) {
                int a, b, k, c; scanf("%d%d%d%d", &a, &b, &k, &c);
                update(a, b, 1, k, c);
            } else {
                int a; scanf("%d", &a);
                printf("%d\n", val[a] + query(a, 1));
            }
        }
    }
    return 0;
}