一些题目没有你想象的那么麻烦

懵逼的 题目

传送至 Luogu

扯淡的 题解

非常水啊..裸的线段树…
注意细节…尤其pushdown…

沙茶的 代码

// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define swap(a, b) {int ____TemP = a; a = b; b = ____TemP;}
using namespace std;
struct node
{
    int lazy; // 1: 0; 2: 1; 3: 鍙栧弽
    int le;
    int ri;
    int l1;
    int l0;
    int r1;
    int r0;
    int zh1;
    int zh0;
    int lx0;
    int lx1;
} b[MAXN << 2];

int n;
int a[MAXN];
void init(int, int, int);
void change(int, int, int, int);
node ask(int, int, int);
inline void pushup(int);
inline void pushdown(int);
inline void ms(int);
int main()
{
    int q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    init(1, 1, n);
    int sre, srx, sry;
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d%d", &sre, &srx, &sry);
        ++sre, ++srx, ++sry;
        if (sre <= 3)
        {
            change(1, srx, sry, sre);
        }
        else
        {
            node out = ask(1, srx, sry);
            if (sre == 4)
            {
                printf("%d\n", out.zh1);
            }
            else
            {
                printf("%d\n", out.lx1);
            }
        }
    }
    return 0;
}
void init(int dq, int le, int ri)
{
    b[dq].le = le, b[dq].ri = ri, b[dq].lazy = 0;
    if (le == ri)
    {
        b[dq].lx1 = b[dq].zh1 = b[dq].l1 = b[dq].r1 = a[le];
        b[dq].lx0 = b[dq].zh0 = b[dq].l0 = b[dq].r0 = 1 - a[le];
        return ;
    }
    int mi = (le + ri) >> 1;
    init(LS(dq), le, mi);
    init(RS(dq), mi + 1, ri);
    pushup(dq);
}
/*
struct node
{
    int lazy; // 0: 0; 1: 1; 2: 鍙栧弽
    int le;
    int ri;

    int l1;
    int l0;
    int r1;
    int r0;
    int zh1;
    int zh0;
    int lx0;
    int lx1;
}b[MAXN << 2];
*/
inline void pushup(int dq)
{
    b[dq].zh1 = b[LS(dq)].zh1 + b[RS(dq)].zh1;
    b[dq].zh0 = b[LS(dq)].zh0 + b[RS(dq)].zh0;
    b[dq].l1 = (b[LS(dq)].zh1 == (b[LS(dq)].ri - b[LS(dq)].le + 1) ? (b[LS(dq)].zh1 + b[RS(dq)].l1) : (b[LS(dq)].l1));
    b[dq].l0 = (b[LS(dq)].zh0 == (b[LS(dq)].ri - b[LS(dq)].le + 1) ? (b[LS(dq)].zh0 + b[RS(dq)].l0) : (b[LS(dq)].l0));
    b[dq].r1 = (b[RS(dq)].zh1 == (b[RS(dq)].ri - b[RS(dq)].le + 1) ? (b[RS(dq)].zh1 + b[LS(dq)].r1) : (b[RS(dq)].r1));
    b[dq].r0 = (b[RS(dq)].zh0 == (b[RS(dq)].ri - b[RS(dq)].le + 1) ? (b[RS(dq)].zh0 + b[LS(dq)].r0) : (b[RS(dq)].r0));
    b[dq].lx1 = max(max(b[LS(dq)].lx1, b[RS(dq)].lx1), b[LS(dq)].r1 + b[RS(dq)].l1);
    b[dq].lx0 = max(max(b[LS(dq)].lx0, b[RS(dq)].lx0), b[LS(dq)].r0 + b[RS(dq)].l0);
}
inline void pushdown(int dq)
{
    int x = b[dq].lazy;
    if (x == 1 || x == 2)
    {
        b[RS(dq)].lazy = b[LS(dq)].lazy = x;
    }
    else
    {
        if (b[RS(dq)].lazy)
        {
            if (b[RS(dq)].lazy == 1)
            {
                b[RS(dq)].lazy = 2;
            }
            else if (b[RS(dq)].lazy == 2)
            {
                b[RS(dq)].lazy = 1;
            }
            else if (b[RS(dq)].lazy == 3)
            {
                b[RS(dq)].lazy = 0;
            }
        }
        else
        {
            b[RS(dq)].lazy = x;
        }
        if (b[LS(dq)].lazy)
        {
            if (b[LS(dq)].lazy == 1)
            {
                b[LS(dq)].lazy = 2;
            }
            else if (b[LS(dq)].lazy == 2)
            {
                b[LS(dq)].lazy = 1;
            }
            else if (b[LS(dq)].lazy == 3)
            {
                b[LS(dq)].lazy = 0;
            }
        }
        else
        {
            b[LS(dq)].lazy = x;
        }
    }
    if (b[LS(dq)].lazy == 3 || (!b[LS(dq)].lazy))
    {
        ms(LS(dq));
    }
    else
    {
        if (b[LS(dq)].lazy == 2)
        {
            b[LS(dq)].l0 = b[LS(dq)].r0 = b[LS(dq)].zh0 = b[LS(dq)].lx0 = 0;
            b[LS(dq)].l1 = b[LS(dq)].r1 = b[LS(dq)].zh1 = b[LS(dq)].lx1 = (b[LS(dq)].ri - b[LS(dq)].le + 1);
        }
        else if (b[LS(dq)].lazy == 1)
        {
            b[LS(dq)].l1 = b[LS(dq)].r1 = b[LS(dq)].zh1 = b[LS(dq)].lx1 = 0;
            b[LS(dq)].l0 = b[LS(dq)].r0 = b[LS(dq)].zh0 = b[LS(dq)].lx0 = (b[LS(dq)].ri - b[LS(dq)].le + 1);
        }
    }
    if (b[RS(dq)].lazy == 3 || (!b[RS(dq)].lazy))
    {
        ms(RS(dq));
    }
    else
    {
        if (b[RS(dq)].lazy == 2)
        {
            b[RS(dq)].l0 = b[RS(dq)].r0 = b[RS(dq)].zh0 = b[RS(dq)].lx0 = 0;
            b[RS(dq)].l1 = b[RS(dq)].r1 = b[RS(dq)].zh1 = b[RS(dq)].lx1 = (b[RS(dq)].ri - b[RS(dq)].le + 1);
        }
        else if (b[RS(dq)].lazy == 1)
        {
            b[RS(dq)].l1 = b[RS(dq)].r1 = b[RS(dq)].zh1 = b[RS(dq)].lx1 = 0;
            b[RS(dq)].l0 = b[RS(dq)].r0 = b[RS(dq)].zh0 = b[RS(dq)].lx0 = (b[RS(dq)].ri - b[RS(dq)].le + 1);
        }
    }
    b[dq].lazy = 0;
}
inline void ms(int dq)
{
    swap(b[dq].l0, b[dq].l1);
    swap(b[dq].r0, b[dq].r1);
    swap(b[dq].zh0, b[dq].zh1);
    swap(b[dq].lx0, b[dq].lx1);
}
void change(int dq, int le, int ri, int zh)
{
    if (b[dq].lazy)
        pushdown(dq);
    if (b[dq].le == le && b[dq].ri == ri)
    {
        b[dq].lazy = zh;
        if (zh == 3)
        {
            ms(dq);
        }
        else
        {
            if (zh == 2)
            {
                b[dq].l0 = b[dq].r0 = b[dq].zh0 = b[dq].lx0 = 0;
                b[dq].l1 = b[dq].r1 = b[dq].zh1 = b[dq].lx1 = (b[dq].ri - b[dq].le + 1);
            }
            else
            {
                b[dq].l1 =b[dq].r1 = b[dq].zh1 = b[dq].lx1 = 0;
                b[dq].l0 = b[dq].r0 = b[dq].zh0 = b[dq].lx0 = (b[dq].ri - b[dq].le + 1);
            }
        }
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
    {
        change(RS(dq), le, ri, zh);
    }
    else if (ri <= mi)
    {
        change(LS(dq), le, ri, zh);
    }
    else
    {
        change(LS(dq), le, mi, zh);
        change(RS(dq), mi + 1, ri, zh);
    }
    pushup(dq);
}
node ask(int dq, int le, int ri)
{
    if (b[dq].lazy)
        pushdown(dq);
    if (b[dq].le == le && b[dq].ri == ri)
    {
        return b[dq];
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
    {
        return ask(RS(dq), le, ri);
    }
    else if (ri <= mi)
    {
        return ask(LS(dq), le, ri);
    }
    else
    {
        node ln = ask(LS(dq), le, mi), rn = ask(RS(dq), mi + 1, ri), re;
        re.le = le, re.ri = ri;
        re.zh1 = ln.zh1 + rn.zh1;
        re.zh0 = ln.zh0 + rn.zh0;
        re.l1 = (ln.zh1 == (ln.ri - ln.le + 1) ? (ln.zh1 + rn.l1) : (ln.l1));
        re.l0 = (ln.zh0 == (ln.ri - ln.le + 1) ? (ln.zh0 + rn.l0) : (ln.l0));
        re.r1 = (rn.zh1 == (rn.ri - rn.le + 1) ? (rn.zh1 + ln.r1) : (rn.r1));
        re.r0 = (rn.zh0 == (rn.ri - rn.le + 1) ? (rn.zh0 + ln.r0) : (rn.r0));
        re.lx1 = max(max(ln.lx1, rn.lx1), ln.r1 + rn.l1);
        re.lx0 = max(max(ln.lx0, rn.lx0), ln.r0 + rn.l0);
        return re;
    }
}

/*
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
*/

By 被罚了4篇+ 作文的 Cansult