HDU 4937 細胞分裂模擬：樹狀數組 + 二分查找替代線段樹

另一種視角：離散化 + BIT

本題核心是維護一個動態增長的序列，只需支持：

1. 單點增加長度
2. 區間所有點長度翻倍
3. 前綴和查詢（定位第 k 個位置屬於哪類）
4. 區間最大值查詢

觀察發現：類型順序固定（1..n），只增長不插入新類型。**樹狀數組（BIT）天然支持單點修改 + 前綴和查詢**，配合二分查找定位位置，區間翻倍可拆解為逐點翻倍（但需優化）。

數據結構設計

long long bit[MAXN];  // BIT 維護前綴和（總長度）
long long cnt[MAXN];  // 陣列維護各類型當前長度（用於區間最大值查詢）
int n, m;

核心操作

BIT 基礎操作

void add(int x, long long v) { for (; x <= n; x += x&-x) bit[x] += v; }
long long sum(int x) { long long r = 0; for (; x; x -= x&-x) r += bit[x]; return r; }

二分查找第 k 個位置所在類型

int get_pos(long long k) { // 找最小 pos 使 sum(pos) >= k
    int l = 1, r = n, ans = n;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (sum(mid) >= k) { ans = mid; r = mid - 1; }
        else l = mid + 1;
    }
    return ans;
}

D 操作處理

int L = get_pos(l), R = get_pos(r);
if (L == R) {
    cnt[L] += r - l + 1;
    add(L, r - l + 1);
} else {
    long long left_part = sum(L) - l + 1;      // L 類型在 [l, ...] 的長度
    long long right_part = r - sum(R - 1);     // R 類型在 [..., r] 的長度
    cnt[L] += left_part; add(L, left_part);
    cnt[R] += right_part; add(R, right_part);
    for (int i = L + 1; i <= R - 1; ++i) {     // 中間完整類型逐個翻倍
        add(i, cnt[i]);
        cnt[i] <<= 1;
    }
}

⚠️ 逐點翻倍循環最坏 O(n)，但實測數據較弱或平均情況可接受。若需嚴格 O(log n)，仍需線段樹懶標記。

Q 操作處理

int L = get_pos(l), R = get_pos(r);
long long ans;
if (L == R) ans = r - l + 1;
else {
    ans = max(sum(L) - l + 1, r - sum(R - 1));
    for (int i = L + 1; i <= R - 1; ++i) ans = max(ans, cnt[i]);
}
printf("%lld\n", ans);

複雜度對比

何時選擇 BIT 方案？

• 數據隨機、中間類型數較少
• 比賽現場快速編寫、調試
• 題目未卡懶標記線段樹的極限數據

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
long long bit[MAXN], cnt[MAXN];
int n, m;
void add(int x, long long v) { for (; x <= n; x += x&-x) bit[x] += v; }
long long sum(int x) { long long r = 0; for (; x; x -= x&-x) r += bit[x]; return r; }
int get_pos(long long k) {
    int l = 1, r = n, ans = n;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (sum(mid) >= k) { ans = mid; r = mid - 1; }
        else l = mid + 1;
    }
    return ans;
}
int main() {
    int T; scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d%d", &n, &m);
        fill(bit, bit+n+1, 0);
        for (int i = 1; i <= n; ++i) cnt[i] = 1, add(i, 1);
        printf("Case #%d:\n", cs);
        while (m--) {
            char op[2]; long long l, r;
            scanf("%s%lld%lld", op, &l, &r);
            if (op[0] == 'D') {
                int L = get_pos(l), R = get_pos(r);
                if (L == R) { cnt[L] += r-l+1; add(L, r-l+1); }
                else {
                    long long lp = sum(L) - l + 1;
                    long long rp = r - sum(R-1);
                    cnt[L] += lp; add(L, lp);
                    cnt[R] += rp; add(R, rp);
                    for (int i = L+1; i <= R-1; ++i) { add(i, cnt[i]); cnt[i] <<= 1; }
                }
            } else {
                int L = get_pos(l), R = get_pos(r);
                long long ans = (L == R) ? r-l+1 : max(sum(L)-l+1, r-sum(R-1));
                for (int i = L+1; i <= R-1; ++i) ans = max(ans, cnt[i]);
                printf("%lld\n", ans);
            }
        }
    }
    return 0;
}

總結

BIT + 二分方案代碼量少、邏輯直觀，適合快速解題；線段樹懶標記方案複雜度嚴格優、通用性強。實戰中根據題目數據範圍、時間限制、自身熟練度靈活選擇。HDU 4937 兩種方案均可 AC，體現了「同一問題，多種數據結構視角」的算法美感。