HDU 3397 Sequence operation：線段樹維護 01 序列區間操作

問題描述

給定長度 N 的 01 序列，支持 5 種操作：

1. 0 a b：區間 [a,b] 賦值 0
2. 1 a b：區間 [a,b] 賦值 1
3. 2 a b：區間 [a,b] 翻轉（0↔1）
4. 3 a b：查詢區間 1 的個數
5. 4 a b：查詢區間連續 1 的最長長度

線段樹節點信息設計

為支持操作 4，每個節點需維護：

• sum[3][2]：
  • sum[0][c]：左側連續 c 的長度
  • sum[1][c]：右側連續 c 的長度
  • sum[2][c]：區間內連續 c 的最大長度
• num：區間 1 的總個數（操作 3）
• 懶標記：
  • setv：-1=無，0/1=區間賦值
  • flip：0/1=區間翻轉

區間合併

Node merge(Node L, Node R) {
    Node X;
    X.l = L.l; X.r = R.r;
    for (int c=0; c<2; c++) {
        X.sum[0][c] = L.sum[0][c];
        X.sum[1][c] = R.sum[1][c];
        X.sum[2][c] = max(L.sum[2][c], R.sum[2][c]);
        if (L.sum[0][c] == L.size()) X.sum[0][c] += R.sum[0][c];
        if (R.sum[1][c] == R.size()) X.sum[1][c] += L.sum[1][c];
        X.sum[2][c] = max(X.sum[2][c], L.sum[1][c] + R.sum[0][c]);
    }
    X.num = L.num + R.num;
    return X;
}

懶標記下推

• 賦值標記優先級高於翻轉：下推時先處理 setv，再處理 flip。
• 賦值 v：num = v * len，sum[*][v] = len，sum[*][!v] = 0，清除 flip。
• 翻轉：swap(sum[*][0], sum[*][1])，num = len - num，flip ^= 1。

核心代碼框架

struct Node {
    int l, r, sum[3][2], num;
    int setv, flip;
    void gao1(int v) { /* 賦值 v */ }
    void gao2() { /* 翻轉 */ }
} node[N*4];

void pushdown(int x) {
    if (node[x].setv != -1) {
        node[lson].gao1(node[x].setv);
        node[rson].gao1(node[x].setv);
        node[x].setv = -1;
    }
    if (node[x].flip) {
        node[lson].gao2();
        node[rson].gao2();
        node[x].flip = 0;
    }
}

void add(int l, int r, int v, int x=0) { // v=0/1/2
    if (node[x].l >= l && node[x].r <= r) {
        if (v == 2) node[x].gao2();
        else node[x].gao1(v);
        return;
    }
    pushdown(x);
    int mid = (node[x].l + node[x].r) / 2;
    if (l <= mid) add(l, r, v, lson);
    if (r > mid) add(l, r, v, rson);
    pushup(x);
}

Node query(int l, int r, int x=0) {
    if (node[x].l >= l && node[x].r <= r) return node[x];
    pushdown(x);
    int mid = (node[x].l + node[x].r) / 2;
    if (l <= mid && r > mid) return merge(query(l,r,lson), query(l,r,rson));
    else if (l <= mid) return query(l,r,lson);
    else return query(l,r,rson);
}

關鍵細節

• 建樹時葉子節點根據初始值 0/1 初始化 sum 和 num。
• 查詢返回 Node 對象，合併時創建臨時節點，避免修改原樹。
• 操作 3 輸出 query(a,b).num；操作 4 輸出 query(a,b).sum[2][1]。
• 下標：題目通常 0-based 或 1-based，代碼中 build(0, n-1) 對應 0-based。

複雜度

• 單次操作/查詢：O(log N)。
• 空間：O(N)。