题目链接：

pid=3397">http://acm.hdu.edu.cn/showproblem.php?pid=3397

题意：给定n个数，由0，1构成。共同拥有5种操作。

每一个操作输入3个数，op，a。b。

1. op == 0。将区间[a，b]赋值为0。
2. op == 1，将区间[a，b]赋值为1；
3. op == 2。将区间[a。b]内的01反转；
4. op == 3。查询区间[a。b]中1的个数。
5. op == 4，查询区间[a。b]中连续1的最大长度。

思路：区间合并 + 区间更新。

每一个结点存7个数：

1. 区间内1的个数c1。
2. 从区间左端点開始连续1的最大长度l1。
3. 以区间右端点结束连续1的最大长度r1。
4. 区间内连续1的最大长度m1。

5. 从区间左端点開始连续0的最大长度l0。
6. 以区间右端点结束连续0的最大长度r0。
7. 区间内连续0的最大长度m0。

记录0的连续是为了反转后统计结果方便。

代码：

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <algorithm>

#include <string>

using namespace std;

#define lson l, m, rt << 1

#define rson m + 1, r, rt << 1 | 1

const int N = 1e5 + 10;

const int INF = 0x7f7f7f7f;

struct Node {

    int c1;

    int l1, r1, m1;

    int l0, r0, m0;

    Node() {}

    Node(int a, int b, int c, int d, int e, int f, int g) {

        c1 = a;

        l1 = b;

        r1 = c;

        m1 = d;

        l0 = e;

        r0 = f;

        m0 = g;

    }

    void reversal(int s) {

        c1 = s;

        swap(l1, l0);

        swap(r1, r0);

        swap(m1, m0);

    }

};

Node node[N << 2];

int cover[N << 2];

int XOR[N << 2];

void pushup(int rt, int l, int r) {

    int m = (l + r) >> 1;

    int lenl = m - l + 1;

    int lenr = r - m;

    node[rt].c1 = node[rt << 1].c1 + node[rt << 1 | 1].c1;

    if (node[rt << 1].l1 == lenl)

        node[rt].l1 = node[rt << 1].l1 + node[rt << 1 | 1].l1;

    else

        node[rt].l1 = node[rt << 1].l1;

    if (node[rt << 1 | 1].r1 == lenr)

        node[rt].r1 = node[rt << 1 | 1].r1 + node[rt << 1].r1;

    else

        node[rt].r1 = node[rt << 1 | 1].r1;

    if (node[rt << 1].l0 == lenl)

        node[rt].l0 = node[rt << 1].l0 + node[rt << 1 | 1].l0;

    else

        node[rt].l0 = node[rt << 1].l0;

    if (node[rt << 1 | 1].r0 == lenr)

        node[rt].r0 = node[rt << 1 | 1].r0 + node[rt << 1].r0;

    else

        node[rt].r0 = node[rt << 1 | 1].r0;

    node[rt].m1 = max(node[rt << 1].r1 + node[rt << 1 | 1].l1,

                    max(node[rt << 1].m1, node[rt << 1 | 1].m1));

    node[rt].m0 = max(node[rt << 1].r0 + node[rt << 1 | 1].l0,

                    max(node[rt << 1].m0, node[rt << 1 | 1].m0));

}

void pushdown(int rt, int l, int r) {

    int m = (l + r) >> 1;

    int lenl = m - l + 1;

    int lenr = r - m;

    if (cover[rt] != -1) {

        if (cover[rt] == 1) {

            node[rt << 1] = Node(lenl, lenl, lenl, lenl, 0, 0, 0);

            node[rt << 1 | 1] = Node(lenr, lenr, lenr, lenr, 0, 0, 0);

        }

        else {

            node[rt << 1] = Node(0, 0, 0, 0, lenl, lenl, lenl);

            node[rt << 1 | 1] = Node(0, 0, 0, 0, lenr, lenr, lenr);

        }

        cover[rt << 1] = cover[rt << 1 | 1] = cover[rt];

        XOR[rt << 1] = XOR[rt << 1 | 1] = 0;

        cover[rt] = -1;

    }

    if (XOR[rt] != 0) {

        node[rt << 1].reversal(lenl - node[rt << 1].c1);

        node[rt << 1 | 1].reversal(lenr - node[rt << 1 | 1].c1);

        if (cover[rt << 1] != -1)

            cover[rt << 1] =  1 - cover[rt << 1];

        else

            XOR[rt << 1] = 1 - XOR[rt << 1];

        if (cover[rt << 1 | 1] != -1)

            cover[rt << 1 | 1] =  1 - cover[rt << 1 | 1];

        else

            XOR[rt << 1 | 1] = 1 - XOR[rt << 1 | 1];

        XOR[rt] = 0;

    }

}

void build(int l, int r, int rt) {

    cover[rt] = -1;

    XOR[rt] = 0;

    if (l == r) {

        int x;

        scanf("%d", &x);

        node[rt] = Node(x, x, x, x, 1 - x, 1 - x, 1 - x);

        return ;

    }

    int m = (l + r) >> 1;

    build(lson);

    build(rson);

    pushup(rt, l, r);

}

void update(int op, int L, int R, int l, int r, int rt) {

    if (L <= l && r <= R) {

        if (op == 2) {

            node[rt].reversal(r - l + 1 - node[rt].c1);

            if (cover[rt] != -1)

                cover[rt] = 1 - cover[rt];

            else

                XOR[rt] = 1 - XOR[rt];

        }

        else {

            node[rt] = (op == 0 ? Node(0, 0, 0, 0, r - l + 1, r - l + 1, r - l + 1) :

                        Node(r - l + 1, r - l + 1, r - l + 1, r - l + 1, 0, 0, 0));

            cover[rt] = op;

            XOR[rt] = 0;

        }

        return ;

    }

    pushdown(rt, l, r);

    int m = (l + r) >> 1;

    if (L <= m)

        update(op, L, R, lson);

    if (R > m)

        update(op, L, R, rson);

    pushup(rt, l, r);

}

Node query(int op, int L, int R, int l, int r, int rt) {

    if (L <= l && r <= R) {

        return node[rt];

    }

    pushdown(rt, l, r);

    int m = (l + r) >> 1;

    Node ql = Node(0, 0, 0, 0, 0, 0, 0);

    Node qr = Node(0, 0, 0, 0, 0, 0, 0);

    if (L <= m)

        ql = query(op, L, R, lson);

    if (R > m)

        qr = query(op, L, R, rson);

    pushup(rt, l, r);

    if (op == 3) {

        return Node(ql.c1 + qr.c1, 0, 0, 0, 0, 0, 0);

    }

    else {

        Node res = Node(0, 0, 0, 0, 0, 0, 0);

        res.m1 = max(ql.r1 + qr.l1, max(ql.m1, qr.m1));

        if (ql.l1 == m - l + 1)

            res.l1 = ql.l1 + qr.l1;

        else

            res.l1 = ql.l1;

        if (qr.r1 == r - m)

            res.r1 = qr.r1 + ql.r1;

        else

            res.r1 = qr.r1;

        return res;

    }

}

int main() {

    int t_case;

    scanf("%d", &t_case);

    for (int i_case = 1; i_case <= t_case; i_case++) {

        int n, m;

        scanf("%d%d", &n, &m);

        build(1, n, 1);

        for (int i = 0; i < m; i++) {

            int op, a, b;

            scanf("%d%d%d", &op, &a, &b);

            a++;

            b++;

            if (op <= 2) {

                update(op, a, b, 1, n, 1);

            }

            else {

                Node res = query(op, a, b, 1, n, 1);

                if (op == 3)

                    printf("%d\n", res.c1);

                else

                    printf("%d\n", res.m1);

            }

        }

    }

    return 0;

}