【題解】POJ 3468. A Simple Problem with Integers

【範例】區間修改 + 懶標記 (Lazy Tag)
【題目敘述】https://vjudge.net/problem/POJ-3468
【解題想法】線段樹 (Segment Tree),區間修改 + 懶標記 (Lazy Tag)

  • Lazy Tag:每次修改區間資料時,只修改「當前區間」的值。「子區間」的值暫時不更新,但會在當前區間的lazy tag留下記號。等到下次query或update需要時,再依照父節點的lazy tag來更新子節點的值,然後把lazy tag傳遞給子節點,同時移除父節點的lazy tag。
  • update( ):
    • 若區間[l, r]完全被[ul, ur]包覆時,更新total[x],同時更新lazy[x]。
    • 否則,先進行push( )。接著處理左右兒子的lazy tag,再update左右兒子。
    • 最後記得pull( )。
  • query( ):
    • 若需要讀取左右兒子的值,要先進行push( ),確保資料正確。
    • 不需要pull( )。
#include <iostream>
using namespace std;

int n, q, a, b, c;
char C;
long long total[100005 << 2], lazy[100005 << 2];

void pull(int x){
    total[x] = total[x<<1] + total[x<<1|1];
}

void push(int x, int l, int r){
    if (lazy[x] == 0) return;
    int mid = (l + r) >> 1;
    lazy[x<<1] += lazy[x];
    lazy[x<<1|1] += lazy[x];
    total[x<<1] += lazy[x] * (mid - l + 1);
    total[x<<1|1] += lazy[x] * (r - mid);
    lazy[x] = 0;
}

void build(int x, int l, int r){
    if (l == r){
        cin >> total[x];
        return;
    }
    int mid = (l + r) >> 1;
    build(x<<1, l, mid);
    build(x<<1|1, mid+1, r);
    pull(x);
}

void update(int x, int l, int r, int ul, int ur){
    //[ul, ur]: 更新區間
    if (ul <= l && r <= ur){
        lazy[x] += c;
        total[x] += c * (r-l+1);
        return;
    }
    push(x, l, r);
    int mid = (l + r) >> 1;
    if (ul <= mid) update(x<<1, l, mid, ul, ur);
    if (mid < ur) update(x<<1|1, mid+1, r, ul, ur);
    pull(x);
}

long long query(int x, int l, int r, int ql, int qr){
    //[ql, qr]: 查詢區間
    if (ql <= l && r <= qr){
        return total[x];
    }
    long long ans = 0;
    int mid = (l + r) >> 1;
    push(x, l, r);
    if (ql <= mid) ans += query(x<<1, l, mid, ql, qr);
    if (mid < qr) ans += query(x<<1|1, mid+1, r, ql, qr);
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n >> q){
        build(1, 1, n);
        for (int i = 0; i < q; i++){
            cin >> C;
            if (C == 'C'){
                cin >> a >> b >> c;
                update(1, 1, n, a, b);
            }else{
                cin >> a >> b;
                cout << query(1, 1, n, a, b) << "\n";
            }
        }
        cout << "\n";
    }
}
分享本文 Share with friends