您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 3911 Black And White：線段樹區間合並維護最長連續黑石

編輯：關於C++

問題描述

n 塊石頭（1 黑，0 白），兩種操作：
1 x y：區間 [x,y] 翻轉顏色。
0 x y：查詢 [x,y] 中最長連續黑石長度。
n, M ≤ 10⁵。

線段樹節點信息（區間合並）

對每個區間 [l,r] 維護 6 個值：
- lmax1：左側連續 1 的最大前綴長度。
- lmax0：左側連續 0 的最大前綴長度。
- rmax1：右側連續 1 的最大後綴長度。
- rmax0：右側連續 0 的最大後綴長度。
- max1：區間內最長連續 1 長度。
- max0：區間內最長連續 0 長度。
另存 lazy 標記（0/1 表示需翻轉）。

關鍵操作

PushUp（合並左右子節點）：
  長度 len = r-l+1，左長 lenL = mid-l+1，右長 lenR = r-mid。
  lmax1 = left.lmax1; if (left.lmax1 == lenL) lmax1 += right.lmax1;
  rmax1 = right.rmax1; if (right.rmax1 == lenR) rmax1 += left.rmax1;
  max1 = max(left.max1, right.max1, left.rmax1 + right.lmax1);
  0 同理。
Apply Flip（翻轉節點）：
swap(lmax1, lmax0); swap(rmax1, rmax0); swap(max1, max0);
lazy ^= 1。
PushDown：將 lazy 傳給子節點（調用 Apply Flip），清空自身 lazy。
Query：區間完全覆蓋返回 max1；否則下推後合併左右結果（注意跨中點情況：min(lenL, left.rmax1) + min(lenR, right.lmax1)）。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
struct Node {
    int lmax1, lmax0, rmax1, rmax0, max1, max0;
    bool lazy;
} seg[MAXN << 2];
int n, m;
void apply(int id) {
    swap(seg[id].lmax1, seg[id].lmax0);
    swap(seg[id].rmax1, seg[id].rmax0);
    swap(seg[id].max1, seg[id].max0);
    seg[id].lazy ^= 1;
}
void pushup(int id, int len) {
    int ls = id<<1, rs = id<<1|1;
    int lenL = (len + 1) >> 1, lenR = len >> 1;
    seg[id].lmax1 = seg[ls].lmax1;
    if (seg[ls].lmax1 == lenL) seg[id].lmax1 += seg[rs].lmax1;
    seg[id].lmax0 = seg[ls].lmax0;
    if (seg[ls].lmax0 == lenL) seg[id].lmax0 += seg[rs].lmax0;
    seg[id].rmax1 = seg[rs].rmax1;
    if (seg[rs].rmax1 == lenR) seg[id].rmax1 += seg[ls].rmax1;
    seg[id].rmax0 = seg[rs].rmax0;
    if (seg[rs].rmax0 == lenR) seg[id].rmax0 += seg[ls].rmax0;
    seg[id].max1 = max({seg[ls].max1, seg[rs].max1, seg[ls].rmax1 + seg[rs].lmax1});
    seg[id].max0 = max({seg[ls].max0, seg[rs].max0, seg[ls].rmax0 + seg[rs].lmax0});
}
void pushdown(int id) {
    if (seg[id].lazy) {
        apply(id<<1);
        apply(id<<1|1);
        seg[id].lazy = false;
    }
}
void build(int id, int l, int r) {
    seg[id].lazy = false;
    if (l == r) {
        int c; scanf("%d", &c);
        if (c == 1) {
            seg[id].lmax1 = seg[id].rmax1 = seg[id].max1 = 1;
            seg[id].lmax0 = seg[id].rmax0 = seg[id].max0 = 0;
        } else {
            seg[id].lmax1 = seg[id].rmax1 = seg[id].max1 = 0;
            seg[id].lmax0 = seg[id].rmax0 = seg[id].max0 = 1;
        }
        return;
    }
    int mid = (l + r) >> 1;
    build(id<<1, l, mid);
    build(id<<1|1, mid+1, r);
    pushup(id, r - l + 1);
}
void update(int id, int l, int r, int L, int R) {
    if (L <= l && r <= R) { apply(id); return; }
    pushdown(id);
    int mid = (l + r) >> 1;
    if (L <= mid) update(id<<1, l, mid, L, R);
    if (R > mid) update(id<<1|1, mid+1, r, L, R);
    pushup(id, r - l + 1);
}
int query(int id, int l, int r, int L, int R) {
    if (L <= l && r <= R) return seg[id].max1;
    pushdown(id);
    int mid = (l + r) >> 1;
    if (R <= mid) return query(id<<1, l, mid, L, R);
    if (L > mid) return query(id<<1|1, mid+1, r, L, R);
    int left = query(id<<1, l, mid, L, R);
    int right = query(id<<1|1, mid+1, r, L, R);
    int cross = min(mid - L + 1, seg[id<<1].rmax1) + min(R - mid, seg[id<<1|1].lmax1);
    return max({left, right, cross});
}
int main() {
    while (~scanf("%d", &n)) {
        build(1, 1, n);
        scanf("%d", &m);
        while (m--) {
            int op, x, y; scanf("%d%d%d", &op, &x, &y);
            if (op == 1) update(1, 1, n, x, y);
            else printf("%d\n", query(1, 1, n, x, y));
        }
    }
    return 0;
}