萌新求调线段树/kel 悬关

six_one @ 2023-10-02 22:39:17

// Problem: P2572 [SCOI2010] 序列操作
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2572
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define ll long long
#define inf 2000000000
using namespace std;

int read()
{
    int num = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
    while(ch <= '9' && ch >= '0') { num = (num << 3) + (num << 1) + (ch - '0'); ch = getchar(); }
    return num * w;
}

ll readll()
{
    ll num = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
    while(ch <= '9' && ch >= '0') { num = (num << 3) + (num << 1) + (ch - '0'); ch = getchar(); }
    return num * w;
}
/*
__int128 read128()
{
    __int128 num = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
    while(ch <= '9' && ch >= '0') { num = (num << 3) + (num << 1) + (ch - '0'); ch = getchar(); }
    return num * w;
}

void print(__int128 n)
{
    if(n < 0)
    {
        putchar('-');
        n *= -1;
    }
    if(n > 9) print(n / 10);
    putchar(n % 10 + '0');
}
上面不用看*/
#define MAXn 100010
#define MAXm 100010
int n, m;
int a[MAXn];

struct SegmentTree
{
    int l, r, ls, rs;
    int num1, num0;
    int lnum1, rnum1;
    int lnum0, rnum0;
    int max1, max0;
    int flag0, flag1, flag2;
} tr[MAXn << 2];

void pushup(int x)
{
    int ls = tr[x].ls, rs = tr[x].rs;

    tr[x].num1 = tr[ls].num1 + tr[rs].num1;
    tr[x].num0 = tr[ls].num0 + tr[rs].num0;

    if(tr[ls].num0 == 0)
        tr[x].lnum1 = tr[ls].num1 + tr[rs].lnum1;
    else tr[x].lnum1 = tr[ls].lnum1;
    if(tr[ls].num1 == 0)
        tr[x].lnum0 = tr[ls].num0 + tr[rs].lnum0;
    else tr[x].lnum0 = tr[ls].lnum0;

    if(tr[rs].num0 == 0)
        tr[x].rnum1 = tr[rs].num1 + tr[ls].rnum1;
    else tr[x].rnum1 = tr[rs].rnum1;
    if(tr[ls].num1 == 0)
        tr[x].rnum0 = tr[rs].num0 + tr[ls].rnum0;
    else tr[x].rnum0 = tr[rs].rnum0;

    tr[x].max1 = max({tr[ls].max1, tr[rs].max1, tr[ls].rnum1 + tr[rs].lnum1});
    tr[x].max0 = max({tr[ls].max0, tr[rs].max0, tr[ls].rnum0 + tr[rs].lnum0});
}

void pushdown(int id)
{
    if(tr[id].flag0)
    {
        int x = tr[id].ls;
        tr[x].flag0 = 1;
        tr[x].flag1 = 0, tr[x].flag2 = 0;
        tr[x].num0 = tr[x].r - tr[x].l + 1;
        tr[x].num1 = 0;

        tr[x].lnum0 = tr[x].num0;
        tr[x].rnum0 = tr[x].num0;

        tr[x].lnum1 = 0;
        tr[x].rnum1 = 0;

        tr[x].max0 = tr[x].num0;
        tr[x].max1 = 0;

        x = tr[id].rs;
        tr[x].flag0 = 1;
        tr[x].flag1 = 0, tr[x].flag2 = 0;
        tr[x].num0 = tr[x].r - tr[x].l + 1;
        tr[x].num1 = 0;

        tr[x].lnum0 = tr[x].num0;
        tr[x].rnum0 = tr[x].num0;

        tr[x].lnum1 = 0;
        tr[x].rnum1 = 0;

        tr[x].max0 = tr[x].num0;
        tr[x].max1 = 0;

        tr[id].flag0 = tr[id].flag1 = tr[id].flag2 = 0;
    }
    else if(tr[id].flag1)
    {
        int x = tr[id].ls;
        tr[x].flag1 = 1;
        tr[x].flag0 = 0, tr[x].flag2 = 0;
        tr[x].num1 = tr[x].r - tr[x].l + 1;
        tr[x].num0 = 0;

        tr[x].lnum1 = tr[x].num1;
        tr[x].rnum1 = tr[x].num1;

        tr[x].lnum0 = 0;
        tr[x].rnum0 = 0;

        tr[x].max1 = tr[x].num1;
        tr[x].max0 = 0;

        x = tr[x].rs;
        tr[x].flag1 = 1;
        tr[x].flag0 = 0, tr[x].flag2 = 0;
        tr[x].num1 = tr[x].r - tr[x].l + 1;
        tr[x].num0 = 0;

        tr[x].lnum1 = tr[x].num1;
        tr[x].rnum1 = tr[x].num1;

        tr[x].lnum0 = 0;
        tr[x].rnum0 = 0;

        tr[x].max1 = tr[x].num1;
        tr[x].max0 = 0;

        tr[id].flag0 = tr[id].flag1 = tr[id].flag2 = 0;
    }
    if(tr[id].flag2)
    {
        int x = tr[id].ls;
        tr[x].flag2 ^= 1;
        swap(tr[x].num1, tr[x].num0);
        swap(tr[x].max1, tr[x].max0);
        swap(tr[x].lnum1, tr[x].lnum0);
        swap(tr[x].rnum1, tr[x].rnum0);

        x = tr[id].rs;
        tr[x].flag2 ^= 1;
        swap(tr[x].num1, tr[x].num0);
        swap(tr[x].max1, tr[x].max0);
        swap(tr[x].lnum1, tr[x].lnum0);
        swap(tr[x].rnum1, tr[x].rnum0);
    }
    tr[id].flag0 = 0, tr[id].flag1 = 0, tr[id].flag2 = 0;
}

void build(int x, int L, int R)
{
    tr[x].l = L, tr[x].r = R;
    if(L == R)
    {
        if(a[L] == 1)
        {
            tr[x].num1 = 1;
            tr[x].lnum1 = 1;
            tr[x].rnum1 = 1;
            tr[x].max1 = 1;
        }
        else
        {
            tr[x].num0 = 1;
            tr[x].lnum0 = 1;
            tr[x].rnum0 = 1;
            tr[x].max0 = 1;
        }
        return;
    }
    int mid = (L + R) >> 1;
    tr[x].ls = x << 1;
    tr[x].rs = x << 1 | 1;
    build(tr[x].ls, L, mid);
    build(tr[x].rs, mid + 1, R);
    pushup(x);
}

void change(int opt, int x, int L, int R)
{
    if(tr[x].l >= L && tr[x].r <= R)
    {
        if(opt == 0)
        {
            tr[x].flag0 = 1;
            tr[x].flag1 = 0, tr[x].flag2 = 0;
            tr[x].num0 = tr[x].r - tr[x].l + 1;
            tr[x].num1 = 0;

            tr[x].lnum0 = tr[x].num0;
            tr[x].rnum0 = tr[x].num0;

            tr[x].lnum1 = 0;
            tr[x].rnum1 = 0;

            tr[x].max0 = tr[x].num0;
            tr[x].max1 = 0;
        }
        else if(opt == 1)
        {
            tr[x].flag1 = 1;
            tr[x].flag0 = 0, tr[x].flag2 = 0;
            tr[x].num1 = tr[x].r - tr[x].l + 1;
            tr[x].num0 = 0;

            tr[x].lnum1 = tr[x].num1;
            tr[x].rnum1 = tr[x].num1;

            tr[x].lnum0 = 0;
            tr[x].rnum0 = 0;

            tr[x].max1 = tr[x].num1;
            tr[x].max0 = 0;
        }
        else if(opt == 2)
        {
            tr[x].flag2 ^= 1;
            swap(tr[x].num1, tr[x].num0);
            swap(tr[x].max1, tr[x].max0);
            swap(tr[x].lnum1, tr[x].lnum0);
            swap(tr[x].rnum1, tr[x].rnum0);
        }
        return;
    }
    pushdown(x);
    int mid = (tr[x].l + tr[x].r) >> 1;
    if(L <= mid) change(opt, tr[x].ls, L, R);
    if(R >= mid + 1) change(opt, tr[x].rs, L, R);
    pushup(x);
}

SegmentTree ask(int opt, int x, int L, int R)
{
    if(tr[x].l >= L && tr[x].r <= R)
        return tr[x];
    pushdown(x);
    SegmentTree lres;
    bool flag = 0;
    int mid = (tr[x].l + tr[x].r) >> 1;
    if(L <= mid) lres = ask(opt, tr[x].ls, L, R), flag = 1;
    if(R >= mid + 1)
    {
        auto rres = ask(opt, tr[x].rs, L, R);
        if(!flag)
        {
            return rres;
        }
        if(opt == 3)
        {
            lres.num1 += rres.num1;
            return lres;
        }
        else
        {
            SegmentTree res;

            res.num1 = lres.num1 + rres.num1;
            res.num0 = lres.num0 + rres.num0;

            if(lres.num0 == 0)
                res.lnum1 = lres.num1 + rres.lnum1;
            else res.lnum1 = lres.lnum1;
            if(lres.num1 == 0)      
                res.lnum0 = lres.num0 + rres.lnum0;
            else res.lnum0 = lres.lnum0;

            if(rres.num0 == 0)
                res.rnum1 = rres.num1 + lres.rnum1;
            else res.rnum1 = rres.rnum1;
            if(lres.num1 == 0)
                res.rnum0 = rres.num0 + lres.rnum0;
            else res.rnum0 = rres.rnum0;

            res.max1 = max({lres.max1, rres.max1, res.lnum1, res.rnum1, lres.rnum1 + rres.lnum1});
            res.max0 = max({lres.max0, rres.max0, res.lnum0, res.rnum0, lres.rnum0 + rres.lnum0});
            res.l = lres.l, res.r = rres.r;
            return res;
        }
    }
    return lres;
}

void work()
{
    n = read(), m = read();
    for(int i = 1; i <= n; i++)
        a[i] = read();
    build(1, 1, n);
    while(m--)
    {
        int opt = read(), l = read(), r = read();
        l++, r++;
        if(opt < 3) change(opt, 1, l, r);
        else if(opt == 3) printf("%d\n", ask(opt, 1, l, r).num1);
        else if(opt == 4) printf("%d\n", ask(opt, 1, l, r).max1);
    }
    return;
}

int main()
{
    int T = 1;
    while(T--)
    {
        work();
    }
    return 0;
}

by six_one @ 2023-10-02 22:40:16

救救孩子吧/dk

by six_one @ 2023-10-02 22:55:44

更改一处

// Problem: P2572 [SCOI2010] 序列操作
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2572
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define ll long long
#define inf 2000000000
using namespace std;

int read()
{
    int num = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
    while(ch <= '9' && ch >= '0') { num = (num << 3) + (num << 1) + (ch - '0'); ch = getchar(); }
    return num * w;
}

ll readll()
{
    ll num = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
    while(ch <= '9' && ch >= '0') { num = (num << 3) + (num << 1) + (ch - '0'); ch = getchar(); }
    return num * w;
}
/*
__int128 read128()
{
    __int128 num = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
    while(ch <= '9' && ch >= '0') { num = (num << 3) + (num << 1) + (ch - '0'); ch = getchar(); }
    return num * w;
}

void print(__int128 n)
{
    if(n < 0)
    {
        putchar('-');
        n *= -1;
    }
    if(n > 9) print(n / 10);
    putchar(n % 10 + '0');
}
*/
#define MAXn 100010
#define MAXm 100010
int n, m;
int a[MAXn];

struct SegmentTree
{
    int l, r, ls, rs;
    int num1, num0;
    int lnum1, rnum1;
    int lnum0, rnum0;
    int max1, max0;
    int flag0, flag1, flag2;
} tr[MAXn << 2];

void pushup(int x)
{
    int ls = tr[x].ls, rs = tr[x].rs;

    tr[x].num1 = tr[ls].num1 + tr[rs].num1;
    tr[x].num0 = tr[ls].num0 + tr[rs].num0;

    if(tr[ls].num0 == 0)
        tr[x].lnum1 = tr[ls].num1 + tr[rs].lnum1;
    else tr[x].lnum1 = tr[ls].lnum1;
    if(tr[ls].num1 == 0)
        tr[x].lnum0 = tr[ls].num0 + tr[rs].lnum0;
    else tr[x].lnum0 = tr[ls].lnum0;

    if(tr[rs].num0 == 0)
        tr[x].rnum1 = tr[rs].num1 + tr[ls].rnum1;
    else tr[x].rnum1 = tr[rs].rnum1;
    if(tr[ls].num1 == 0)
        tr[x].rnum0 = tr[rs].num0 + tr[ls].rnum0;
    else tr[x].rnum0 = tr[rs].rnum0;

    tr[x].max1 = max({tr[ls].max1, tr[rs].max1, tr[ls].rnum1 + tr[rs].lnum1});
    tr[x].max0 = max({tr[ls].max0, tr[rs].max0, tr[ls].rnum0 + tr[rs].lnum0});
}

void pushdown(int id)
{
    if(tr[id].flag0)
    {
        int x = tr[id].ls;
        tr[x].flag0 = 1;
        tr[x].flag1 = 0, tr[x].flag2 = 0;
        tr[x].num0 = tr[x].r - tr[x].l + 1;
        tr[x].num1 = 0;

        tr[x].lnum0 = tr[x].num0;
        tr[x].rnum0 = tr[x].num0;

        tr[x].lnum1 = 0;
        tr[x].rnum1 = 0;

        tr[x].max0 = tr[x].num0;
        tr[x].max1 = 0;

        x = tr[id].rs;
        tr[x].flag0 = 1;
        tr[x].flag1 = 0, tr[x].flag2 = 0;
        tr[x].num0 = tr[x].r - tr[x].l + 1;
        tr[x].num1 = 0;

        tr[x].lnum0 = tr[x].num0;
        tr[x].rnum0 = tr[x].num0;

        tr[x].lnum1 = 0;
        tr[x].rnum1 = 0;

        tr[x].max0 = tr[x].num0;
        tr[x].max1 = 0;
    }
    else if(tr[id].flag1)
    {
        int x = tr[id].ls;
        tr[x].flag1 = 1;
        tr[x].flag0 = 0, tr[x].flag2 = 0;
        tr[x].num1 = tr[x].r - tr[x].l + 1;
        tr[x].num0 = 0;

        tr[x].lnum1 = tr[x].num1;
        tr[x].rnum1 = tr[x].num1;

        tr[x].lnum0 = 0;
        tr[x].rnum0 = 0;

        tr[x].max1 = tr[x].num1;
        tr[x].max0 = 0;

        x = tr[x].rs;
        tr[x].flag1 = 1;
        tr[x].flag0 = 0, tr[x].flag2 = 0;
        tr[x].num1 = tr[x].r - tr[x].l + 1;
        tr[x].num0 = 0;

        tr[x].lnum1 = tr[x].num1;
        tr[x].rnum1 = tr[x].num1;

        tr[x].lnum0 = 0;
        tr[x].rnum0 = 0;

        tr[x].max1 = tr[x].num1;
        tr[x].max0 = 0;
    }
    if(tr[id].flag2)
    {
        int x = tr[id].ls;
        tr[x].flag2 ^= 1;
        swap(tr[x].num1, tr[x].num0);
        swap(tr[x].max1, tr[x].max0);
        swap(tr[x].lnum1, tr[x].lnum0);
        swap(tr[x].rnum1, tr[x].rnum0);

        x = tr[id].rs;
        tr[x].flag2 ^= 1;
        swap(tr[x].num1, tr[x].num0);
        swap(tr[x].max1, tr[x].max0);
        swap(tr[x].lnum1, tr[x].lnum0);
        swap(tr[x].rnum1, tr[x].rnum0);
    }
    tr[id].flag0 = 0, tr[id].flag1 = 0, tr[id].flag2 = 0;
}

void build(int x, int L, int R)
{
    tr[x].l = L, tr[x].r = R;
    if(L == R)
    {
        if(a[L] == 1)
        {
            tr[x].num1 = 1;
            tr[x].lnum1 = 1;
            tr[x].rnum1 = 1;
            tr[x].max1 = 1;
        }
        else
        {
            tr[x].num0 = 1;
            tr[x].lnum0 = 1;
            tr[x].rnum0 = 1;
            tr[x].max0 = 1;
        }
        return;
    }
    int mid = (L + R) >> 1;
    tr[x].ls = x << 1;
    tr[x].rs = x << 1 | 1;
    build(tr[x].ls, L, mid);
    build(tr[x].rs, mid + 1, R);
    pushup(x);
}

void change(int opt, int x, int L, int R)
{
    if(tr[x].l >= L && tr[x].r <= R)
    {
        if(opt == 0)
        {
            tr[x].flag0 = 1;
            tr[x].flag1 = 0, tr[x].flag2 = 0;
            tr[x].num0 = tr[x].r - tr[x].l + 1;
            tr[x].num1 = 0;

            tr[x].lnum0 = tr[x].num0;
            tr[x].rnum0 = tr[x].num0;

            tr[x].lnum1 = 0;
            tr[x].rnum1 = 0;

            tr[x].max0 = tr[x].num0;
            tr[x].max1 = 0;
        }
        else if(opt == 1)
        {
            tr[x].flag1 = 1;
            tr[x].flag0 = 0, tr[x].flag2 = 0;
            tr[x].num1 = tr[x].r - tr[x].l + 1;
            tr[x].num0 = 0;

            tr[x].lnum1 = tr[x].num1;
            tr[x].rnum1 = tr[x].num1;

            tr[x].lnum0 = 0;
            tr[x].rnum0 = 0;

            tr[x].max1 = tr[x].num1;
            tr[x].max0 = 0;
        }
        else if(opt == 2)
        {
            tr[x].flag2 ^= 1;
            swap(tr[x].num1, tr[x].num0);
            swap(tr[x].max1, tr[x].max0);
            swap(tr[x].lnum1, tr[x].lnum0);
            swap(tr[x].rnum1, tr[x].rnum0);
        }
        return;
    }
    pushdown(x);
    int mid = (tr[x].l + tr[x].r) >> 1;
    if(L <= mid) change(opt, tr[x].ls, L, R);
    if(R >= mid + 1) change(opt, tr[x].rs, L, R);
    pushup(x);
}

SegmentTree ask(int opt, int x, int L, int R)
{
    if(tr[x].l >= L && tr[x].r <= R)
        return tr[x];
    pushdown(x);
    SegmentTree lres;
    bool flag = 0;
    int mid = (tr[x].l + tr[x].r) >> 1;
    if(L <= mid) lres = ask(opt, tr[x].ls, L, R), flag = 1;
    if(R >= mid + 1)
    {
        auto rres = ask(opt, tr[x].rs, L, R);
        if(!flag)
        {
            return rres;
        }
        if(opt == 3)
        {
            lres.num1 += rres.num1;
            return lres;
        }
        else
        {
            SegmentTree res;

            res.num1 = lres.num1 + rres.num1;
            res.num0 = lres.num0 + rres.num0;

            if(lres.num0 == 0)
                res.lnum1 = lres.num1 + rres.lnum1;
            else res.lnum1 = lres.lnum1;
            if(lres.num1 == 0)      
                res.lnum0 = lres.num0 + rres.lnum0;
            else res.lnum0 = lres.lnum0;

            if(rres.num0 == 0)
                res.rnum1 = rres.num1 + lres.rnum1;
            else res.rnum1 = rres.rnum1;
            if(lres.num1 == 0)
                res.rnum0 = rres.num0 + lres.rnum0;
            else res.rnum0 = rres.rnum0;

            res.max1 = max({lres.max1, rres.max1, res.lnum1, res.rnum1, lres.rnum1 + rres.lnum1});
            res.max0 = max({lres.max0, rres.max0, res.lnum0, res.rnum0, lres.rnum0 + rres.lnum0});
            res.l = lres.l, res.r = rres.r;
            return res;
        }
    }
    return lres;
}

void work()
{
    n = read(), m = read();
    for(int i = 1; i <= n; i++)
        a[i] = read();
    build(1, 1, n);
    while(m--)
    {
        int opt = read(), l = read(), r = read();
        l++, r++;
        if(opt < 3) change(opt, 1, l, r);
        else if(opt == 3) printf("%d\n", ask(opt, 1, l, r).num1);
        else if(opt == 4) printf("%d\n", ask(opt, 1, l, r).max1);
    }
    return;
}

int main()
{
    int T = 1;
    while(T--)
    {
        work();
    }
    return 0;
}

by six_one @ 2023-10-03 18:56:35

已A，此贴终，l打成了r