ZOJ 2706 Thermal Death of the Universe：線段樹區間賦值與區間求和

ZOJ 2706 Thermal Death of the Universe：線段樹區間賦值與區間求和

題目大意

初始有 n 個數。m 次操作：將區間 [l, r] 所有數替換為它們的平均值。平均值非整數時，若當前總和 ≤ 原始總和則向上取整，否則向下取整。最終輸出所有數。

線段樹設計

• 節點存儲：sum（區間和）、col（懶標記，-1 表示無標記，否為統一賦值）。
• 區間賦值：update(L, R, val) 將區間設為 val，更新 sum 和 col。
• 下推標記：push_down 將父節點的 col 傳給左右子，更新子節點 sum，清空父節點 col。
• 區間查詢：query(L, R) 返回區間和，查詢前必須 push_down。

平均值取整規則處理

double ave = (double)sum / len;
long long val;
if (ave == (long long)ave) val = (long long)ave;
else {
    long long cur_total = query(1, n);
    if (cur_total <= original_total) {
        val = (ave > 0) ? (long long)ave + 1 : (long long)ave; // 向上取整
    } else {
        val = (ave > 0) ? (long long)ave : (long long)ave - 1; // 向下取整
    }
}

完整代碼框架

#include 
#include 
using namespace std;
const int MAXN = 30010;
long long sum[MAXN<<2], col[MAXN<<2];
long long a[MAXN];
int n, m;

void push_up(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; }
void push_down(int rt, int len) {
    if (col[rt] != -1) {
        col[rt<<1] = col[rt<<1|1] = col[rt];
        sum[rt<<1] = col[rt] * (len - (len>>1));
        sum[rt<<1|1] = col[rt] * (len>>1);
        col[rt] = -1;
    }
}
void build(int l, int r, int rt) {
    col[rt] = -1;
    if (l == r) { sum[rt] = a[l]; return; }
    int mid = (l+r)>>1;
    build(l, mid, rt<<1);
    build(mid+1, r, rt<<1|1);
    push_up(rt);
}
void update(int L, int R, long long val, int l, int r, int rt) {
    if (L <= l && r <= R) { col[rt] = val; sum[rt] = val * (r-l+1); return; }
    push_down(rt, r-l+1);
    int mid = (l+r)>>1;
    if (L <= mid) update(L, R, val, l, mid, rt<<1);
    if (R > mid) update(L, R, val, mid+1, r, rt<<1|1);
    push_up(rt);
}
long long query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) return sum[rt];
    push_down(rt, r-l+1);
    int mid = (l+r)>>1;
    long long ret = 0;
    if (L <= mid) ret += query(L, R, l, mid, rt<<1);
    if (R > mid) ret += query(L, R, mid+1, r, rt<<1|1);
    return ret;
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        for (int i=1;i<=n;i++) scanf("%lld", &a[i]);
        build(1, n, 1);
        long long original_total = query(1, n, 1, n, 1);
        while (m--) {
            int l, r; scanf("%d%d", &l, &r);
            long long seg_sum = query(l, r, 1, n, 1);
            // 計算 val（見上方取整規則）
            update(l, r, val, 1, n, 1);
        }
        for (int i=1;i<=n;i++) {
            printf("%lld%c", query(i,i,1,n,1), i==n?'\n':' ');
        }
    }
    return 0;
}

關鍵點總結

• 線段樹支援區間賦值（覆蓋）與區間求和，懶標記為 col（-1 為無標記）。
• 平均值取整規則需比較當前總和與原始總和，注意負數向上/向下取整方向相反。
• 最終逐點查詢輸出。