信息学做题日记：耗时4天，终于AC掉一道题

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX_NUM = 1e5 + 5;

struct line {
    int l, r, len, sum, max_zero, max_one, left_zero, right_zero, left_one, right_one;
    int lazy, add;
} t[8 * MAX_NUM];

int a[MAX_NUM];

void push_up(int u) {
    auto &root = t[u];
    auto &left = t[u << 1];
    auto &right = t[u << 1 | 1];
    if (left.left_zero == left.len) {
        root.left_zero = left.left_zero + right.left_zero;
    } else {
        root.left_zero = left.left_zero;
    }
    if (left.left_one == left.len) {
        root.left_one = left.left_one + right.left_one;
    } else {
        root.left_one = left.left_one;
    }
    if (right.right_zero == right.len) {
        root.right_zero = right.right_zero + left.right_zero;
    } else {
        root.right_zero = right.right_zero;
    }
    if (right.right_one == right.len) {
        root.right_one = right.right_one + left.right_one;
    } else {
        root.right_one = right.right_one;
    }
    root.max_zero = max({left.max_zero, right.max_zero,
                         left.right_zero + right.left_zero});
    root.max_one = max({left.max_one, right.max_one,
                        left.right_one + right.left_one});
    root.sum = left.sum + right.sum;
}

void build(int u, int l, int r) {
    t[u].l = l;
    t[u].r = r;
    t[u].len = r - l + 1;
    t[u].lazy = -1;
    if (l == r) {
        t[u].left_zero = 1 - a[l];
        t[u].left_one = a[l];
        t[u].right_zero = 1 - a[l];
        t[u].right_one = a[l];
        t[u].max_zero = 1 - a[l];
        t[u].max_one = a[l];
        t[u].sum = a[l];
        return;
    }  else {
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid +1 , r);
        push_up(u);
    }
}

void change(line &x,  bool flag) {
    x.sum = 0;
    x.left_one = 0;
    x.right_one = 0;
    x.left_zero = x.len;
    x.right_zero = x.len;
    x.max_zero = x.len;
    x.max_one = 0;
    if(flag) {
        swap(x.left_one, x.left_zero);
        swap(x.right_one, x.right_zero);
        swap(x.max_one, x.max_zero);
        x.sum = x.len;
    }
}

void change2(line &x) {
    swap(x.left_one, x.left_zero);
    swap(x.right_one, x.right_zero);
    swap(x.max_one, x.max_zero);
    x.sum = x.len - x.sum;
}

void push_down(int u) {
    auto &root = t[u];
    auto &left = t[u << 1];
    auto &right = t[u << 1 | 1];
    if (root.lazy == 0) {
        change(left,  false);
        change(right, false);
    } else if (root.lazy == 1) {
        change(left, true);
        change(right, true);
    }
    if (root.lazy != -1) {
        root.add = 0;
        left.lazy = root.lazy;
        right.lazy = root.lazy;
        left.add = 0;
        right.add = 0;
    }
    if (root.add == 1) {
        root.add = 0;
        if (left.lazy != -1) {
            left.lazy ^= 1;
        } else {
            left.add ^= 1;
        }
        if (right.lazy != -1) {
            right.lazy ^= 1;
        } else {
            right.add ^= 1;
        }
        change2(left);
        change2(right);
    }
    root.lazy = -1;
}

void modify(int u, int l, int r, int opt) {
    push_down(u);
    if (t[u].l >= l && t[u].r <= r) {
        if (opt == 1) {
            change(t[u],  false);
            t[u].lazy = 0;
        } else if (opt == 2) {
            change(t[u],  true);
            t[u].lazy = 1;
        } else if(opt == 3) {
            change2(t[u]);
            t[u].add ^= 1;
        }
        return;
    } else {
        int mid = (t[u].l + t[u].r) >> 1;
        if (l <= mid) {
            modify(u << 1, l, r, opt);
        }
        if (r > mid) {
            modify(u << 1 | 1, l, r, opt);
        }
        push_up(u);
    }
}

int query(int u, int l, int r) {
    if (t[u].l >= l && t[u].r <= r) {
        return t[u].sum;
    }

    push_down(u);

    int mid = (t[u].l + t[u].r) >> 1;
    int s = 0;
    if (l <= mid) {
        s = query(u << 1, l, r);
    }
    if (r > mid) {
        s += query(u << 1 | 1, l, r);
    }
    return s;
}
//line p, q, ans;

line cnt(int u, int l, int r) {

    if (t[u].l >= l && t[u].r <= r) {
        return t[u];
    } else {
        push_down(u);
        int mid = (t[u].l + t[u].r) >> 1;
        line p = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        line q = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        line ans = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        if (l <= mid) {
            p = cnt(u << 1, l, r);
            ans.max_one = p.max_one;
        }
        if (r > mid) {
            q = cnt(u << 1 | 1, l, r);
            ans.max_one = max(ans.max_one, q.max_one);
        }
        ans.max_one = max(p.right_one + q.left_one, ans.max_one);
        if (p.left_one == p.len) {
            ans.left_one = p.left_one + q.left_one;
        } else {
            ans.left_one = p.left_one;
        }
        if (q.right_one == q.len) {
            ans.right_one = p.right_one + q.right_one;
        } else {
            ans.right_one = q.right_one;
        }
        return ans;
    }
}

void best_coder() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(1,1,n);
    for (int i = 0; i < m; ++i) {
        int opt, l, r;
        cin >> opt >> l >> r;
        ++opt;
        ++l;
        ++r;
        if(opt <= 3){
            modify(1, l, r, opt);
        } else if (opt == 4) {
            cout << query(1, l, r) << '\n';
        } else {
            cout << cnt(1, l, r).max_one << '\n';
        }
    }
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}