Sequence operation HDU - 3397 (线

题目来源：Sequence operation

题意

给你一个长度为n的01串，现在有m次操作

0 a b表示把区间[a, b]全部变为0

1 a b表示把区间[a, b]全部变为1

2 a b表示把区间[a, b]翻转，0变1,1变0

3 a b输出区间[a, b]中1的个数

4 a b输出区间[a, b]中最长连续的1的长度

思路

用线段树维护区间从左、右开始数0和1的最大长度，区间内01的最大长度，区间内1的数量和区间是否翻转

由于一个区间翻转偶数次后的结果和初始结果一致，所以如果区间在已有翻转标记的情况下再增添一个翻转标记则无需翻转

注意此题需要将pushdown在查询和更新的最开始处下推，不然会有标记推不下去。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
const int N = 100010;
int a[N];
inline int max(int x, int y) { return x > y ? x : y; }
inline int min(int x, int y) { return x > y ? y : x; }
namespace SEG
{
    struct Tag
    {
        int lzero, rzero, mzero;
        int lone, rone, mone;
        int sum;
        int lazy, x_or;
    } c[N << 2];
    inline void pushDown(int k, int l, int r)
    {
        if (l == r)    return;
        int mid = (l + r) >> 1;
        if (c[k].lazy != -1)
        {
            c[k << 1].lazy = c[k << 1 | 1].lazy = c[k].lazy;
            c[k << 1].x_or = c[k << 1 | 1].x_or = 0;
            if (c[k].lazy == 0)
            {
                c[k << 1].lzero = c[k << 1].rzero = c[k << 1].mzero = mid - l + 1;
                c[k << 1].sum = c[k << 1].lone = c[k << 1].rone = c[k << 1].mone = 0;
                c[k << 1 | 1].lzero = c[k << 1 | 1].rzero = c[k << 1 | 1].mzero = r - mid;
                c[k << 1 | 1].sum = c[k << 1 | 1].lone = c[k << 1 | 1].rone = c[k << 1 | 1].mone = 0;
            }
            else if (c[k].lazy == 1)
            {
                c[k << 1].lzero = c[k << 1].rzero = c[k << 1].mzero = 0;
                c[k << 1].sum = c[k << 1].lone = c[k << 1].rone = c[k << 1].mone = mid - l + 1;
                c[k << 1 | 1].lzero = c[k << 1 | 1].rzero = c[k << 1 | 1].mzero = 0;
                c[k << 1 | 1].sum = c[k << 1 | 1].lone = c[k << 1 | 1].rone = c[k << 1 | 1].mone = r - mid;
            }
            c[k].lazy = -1;
        }
        if (c[k].x_or)
        {
            c[k << 1].x_or ^= 1;
            c[k << 1 | 1].x_or ^= 1;

            std::swap(c[k << 1].lzero, c[k << 1].lone);
            std::swap(c[k << 1].rzero, c[k << 1].rone);
            std::swap(c[k << 1].mzero, c[k << 1].mone);
            c[k << 1].sum = mid - l + 1 - c[k << 1].sum;

            std::swap(c[k << 1 | 1].lzero, c[k << 1 | 1].lone);
            std::swap(c[k << 1 | 1].rzero, c[k << 1 | 1].rone);
            std::swap(c[k << 1 | 1].mzero, c[k << 1 | 1].mone);
            c[k << 1 | 1].sum = (r - mid) - c[k << 1 | 1].sum;

            c[k].x_or = 0;
        }
    }
    inline void pushUp(int k, int l, int r)
    {
        int mid = (l + r) >> 1;

        c[k].lzero = c[k << 1].lzero;
        c[k].rzero = c[k << 1 | 1].rzero;
        if (c[k].lzero >= mid - l + 1)
            c[k].lzero += c[k << 1 | 1].lzero;
        if (c[k].rzero >= r - mid)
            c[k].rzero += c[k << 1].rzero;
        c[k].mzero = max(c[k << 1].rzero + c[k << 1 | 1].lzero, max(c[k << 1].mzero, c[k << 1 | 1].mzero));

        c[k].lone = c[k << 1].lone;
        c[k].rone = c[k << 1 | 1].rone;
        if (c[k].lone >= mid - l + 1)
            c[k].lone += c[k << 1 | 1].lone;
        if (c[k].rone >= r - mid)
            c[k].rone += c[k << 1].rone;
        c[k].mone = max(c[k << 1].rone + c[k << 1 | 1].lone, max(c[k << 1].mone, c[k << 1 | 1].mone));

        c[k].sum = c[k << 1].sum + c[k << 1 | 1].sum;
    }
    void build(int k, int l, int r)
    {
        c[k].lazy = -1;
        c[k].x_or = 0;
        if (l == r)
        {
            if (a[l] == 0)
            {
                c[k].lzero = c[k].rzero = c[k].mzero = 1;
                c[k].sum = c[k].lone = c[k].rone = c[k].mone = 0;
            }
            else if (a[l] == 1)
            {
                c[k].lzero = c[k].rzero = c[k].mzero = 0;
                c[k].sum = c[k].lone = c[k].rone = c[k].mone = 1;
            }
            return;
        }
        int mid = (l + r) >> 1;

        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);

        pushUp(k, l, r);
    }
    // l, r是总区间 left, right是查询区间
    int query_sum(int k, int l, int r, int left, int right)
    {
        pushDown(k, l, r);
        if (left <= l && r <= right)    return c[k].sum;

        int ans = 0;

        int mid = (l + r) >> 1;
        if (left <= mid)    ans += query_sum(k << 1, l, mid, left, right);
        if (mid < right)    ans += query_sum(k << 1 | 1, mid + 1, r, left, right);

        return ans;
    }
    int query_max(int k, int l, int r, int left, int right)
    {
        pushDown(k, l, r);
        if (left <= l && r <= right)    return c[k].mone;

        int ans = 0;

        int mid = (l + r) >> 1;
        if (left <= mid)    ans = max(ans, query_max(k << 1, l, mid, left, right));
        if (mid < right)    ans = max(ans, query_max(k << 1 | 1, mid + 1, r, left, right));

        return max(ans, min(c[k << 1].rone, mid - left + 1) + min(c[k << 1 | 1].lone, right - mid));
    }
    // l, r是总区间 left, right是查询区间，k是起始节点编号，val是更新的值
    void update(int k, int l, int r, int left, int right, int val)
    {
        pushDown(k, l, r);
        if (left <= l && r <= right)
        {
            if (val == 0)
            {
                c[k].lazy = val;
                c[k].lzero = c[k].rzero = c[k].mzero = r - l + 1;
                c[k].sum = c[k].lone = c[k].rone = c[k].mone = 0;
            }
            else if (val == 1)
            {
                c[k].lazy = val;
                c[k].lzero = c[k].rzero = c[k].mzero = 0;
                c[k].sum = c[k].lone = c[k].rone = c[k].mone = r - l + 1;
            }
            else if (val == 2)
            {
                c[k].x_or = 1;

                std::swap(c[k].lzero, c[k].lone);
                std::swap(c[k].rzero, c[k].rone);
                std::swap(c[k].mzero, c[k].mone);
                c[k].sum = (r - l + 1) - c[k].sum;
            }
            return;
        }

        int mid = (l + r) >> 1;
        if (left <= mid)    update(k << 1, l, mid, left, right, val);
        if (mid < right)    update(k << 1 | 1, mid + 1, r, left, right, val);

        pushUp(k, l, r);
    }
}
int n, m;
int main()
{
    using namespace SEG;
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)    scanf("%d", a + i);
        memset(c, 0, sizeof(c));
        build(1, 1, n);
        int op, x, y;
        for (int i = 1; i <= m; ++i)
        {
            scanf("%d%d%d", &op, &x, &y);
            x++; y++;
            switch (op)
            {
            case 0:
            case 1:
            case 2:
                update(1, 1, n, x, y, op);
                break;
            case 3:
                printf("%d\n", query_sum(1, 1, n, x, y));
                break;
            case 4:
                printf("%d\n", query_max(1, 1, n, x, y));
                break;
            default:
                break;
            }
        }
    }
    return 0;
}