CodeForces #248 A/B 題解：蘋果分配與區間求和

A 題：蘋果公平分配

只有 100g 和 200g 蘋果，判斷能否分成等重兩堆。

核心邏輯

• 統計 cnt100、cnt200
• 若 cnt200 為偶數：需 cnt100 也為偶數
• 若 cnt200 為奇數：需 cnt100 ≥ 2 且 (cnt100-2) 為偶數（兩個 100g 合成一個 200g）

時間 O(n)，空間 O(1)。

B 題：區間求和（線段樹 / 前綴和）

兩類查詢：原數組區間和、排序後數組區間和。官方解法用前綴和更簡潔：

// 預處理
sort(a+1, a+n+1);
for (i=1; i<=n; ++i) {
    sum[0][i] = sum[0][i-1] + original[i];
    sum[1][i] = sum[1][i-1] + a[i];
}
// 查詢
ans = sum[type-1][r] - sum[type-1][l-1];

作者最初用雙線段樹，後發現前綴和足夠，體現「Done is better than perfect」。

心得

• A 題：仔細分析奇偶性，別想太複雜
• B 題：靜態區間和首選前綴和，線段樹適合動態更新