HDU 4937 細胞分裂模擬：線段樹維護區間翻倍與最大值查詢

問題建模

初始隊列：第 i 位置為類型 i 的細胞（1 ≤ i ≤ n）。操作：

• D l r：區間 [l, r] 內每個細胞分裂一次（數量翻倍）
• Q l r：查詢區間 [l, r] 內同類型細胞的最大數量

關鍵約束：n, m ≤ 50,000，但操作後隊列長度可達 1e8，不能顯式展開隊列。需用數據結構維護「壓縮表示」。

核心觀察：類型邊界不變，只擴展長度

初始每類型佔 1 格。分裂操作只會在區間內將現有類型的長度翻倍，**不會改變類型順序，也不會產生新類型**。因此可用線段樹維護：

• 葉節點：對應原始類型 1..n，存儲當前長度 len[i]
• 內部節點：維護區間總長度 sum、區間最大長度 mx
• 懶標記：tag 表示該區間整體翻倍次數（乘法標記）

線段樹節點設計

struct Node {
    long long sum;  // 區間總長度
    long long mx;   // 區間最大單類型長度
    int tag;        // 待下推的翻倍次數（乘法懶標記）
} tr[4 * MAXN];

關鍵操作實現

Build：初始化

void build(int u, int l, int r) {
    tr[u].tag = 0;
    if (l == r) { tr[u].sum = tr[u].mx = 1; return; }
    int mid = (l + r) >> 1;
    build(u<<1, l, mid); build(u<<1|1, mid+1, r);
    pushup(u);
}

Pushdown：懶標記下推（乘法）

void pushdown(int u) {
    if (tr[u].tag) {
        int t = tr[u].tag;
        apply(u<<1, t); apply(u<<1|1, t);
        tr[u].tag = 0;
    }
}
void apply(int u, int t) {
    tr[u].sum <<= t;        // 總長度 × 2^t
    tr[u].mx  <<= t;        // 最大長度 × 2^t
    tr[u].tag += t;         // 累加翻倍次數
}

注意：翻倍次數最多 log2(1e8) < 27，int 足夠，但 sum/mx 必須用 long long。

區間翻倍更新

void update_double(int u, int l, int r, int L, int R) {
    if (L <= l && r <= R) { apply(u, 1); return; }
    pushdown(u);
    int mid = (l + r) >> 1;
    if (L <= mid) update_double(u<<1, l, mid, L, R);
    if (R > mid) update_double(u<<1|1, mid+1, r, L, R);
    pushup(u);
}

單點增量更新（處理部分覆蓋）

查詢/更新的區間 [l, r] 可能只部分覆蓋某類型，需將該類型拆分：

void update_add(int u, int l, int r, int pos, long long val) {
    if (l == r) { tr[u].sum += val; tr[u].mx += val; return; }
    pushdown(u);
    int mid = (l + r) >> 1;
    if (pos <= mid) update_add(u<<1, l, mid, pos, val);
    else update_add(u<<1|1, mid+1, r, pos, val);
    pushup(u);
}

位置定位：第 k 個細胞屬於哪個原始類型

int query_pos(int u, int l, int r, long long k, bool is_left) {
    if (l == r) { return l; }
    pushdown(u);
    int mid = (l + r) >> 1;
    if (k <= tr[u<<1].sum) return query_pos(u<<1, l, mid, k, is_left);
    else return query_pos(u<<1|1, mid+1, r, k - tr[u<<1].sum, is_left);
}

區間最大值查詢

long long query_max(int u, int l, int r, int L, int R) {
    if (L <= l && r <= R) return tr[u].mx;
    pushdown(u);
    int mid = (l + r) >> 1;
    long long ans = 0;
    if (L <= mid) ans = max(ans, query_max(u<<1, l, mid, L, R));
    if (R > mid) ans = max(ans, query_max(u<<1|1, mid+1, r, L, R));
    return ans;
}

處理操作的完整邏輯

D l r（翻倍）

1. 定位 l 所在類型 L = query_pos(l)，r 所在類型 R = query_pos(r)
2. 若 L == R：單點增加 r-l+1
3. 否則：
   • 左端類型 L：增加 sum[L] - l + 1
   • 右端類型 R：增加 r - sum[R-1]
   • 中間完整類型 [L+1, R-1]：區間翻倍

Q l r（查詢最大值）

1. 同樣定位 L, R
2. 若 L == R：答案 r-l+1
3. 否則：max(左端增量, 右端增量, query_max(L+1, R-1))

複雜度分析

• 建樹：O(n)
• 單次操作：O(log n) 定位 + O(log n) 更新/查詢 = O(log n)
• 總時間：O((n + m) log n) ≈ 5e4 × 16，極快
• 空間：O(n) 線段樹

避坑指南

1. 長整型：所有長度、總和、答案用 long long
2. 懶標記乘法：sum <<= tag 等價 sum *= (1LL << tag)，注意 tag 累加而非覆蓋
3. 邊界條件：L+1 > R-1 時跳過區間操作
4. 輸入讀取：scanf("%s%lld%lld", op, &l, &r)，op[0] 判斷 'D'/'Q'

完整代碼框架

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
struct Node { long long sum, mx; int tag; } tr[MAXN<<2];
int n, m;
void build(int u, int l, int r) { ... }
void apply(int u, int t) { ... }
void pushdown(int u) { ... }
void pushup(int u) { tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum; tr[u].mx = max(tr[u<<1].mx, tr[u<<1|1].mx); }
void update_double(int u, int l, int r, int L, int R) { ... }
void update_add(int u, int l, int r, int pos, long long val) { ... }
int query_pos(int u, int l, int r, long long k) { ... }
long long query_max(int u, int l, int r, int L, int R) { ... }
int main() {
    int T; scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d%d", &n, &m);
        build(1, 1, n);
        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') { /* 翻倍邏輯 */ }
            else { /* 查詢邏輯 */ }
        }
    }
    return 0;
}