0 分线段树求调喵

0000pnc @ 2023-05-05 21:11:32

by 0000pnc @ 2023-05-05 21:11:49

#include <bits/stdc++.h>
using namespace std;

int n, m, p[100005];

// sgt_start
#define lson (id << 1)
#define rson ((id << 1) | 1)

struct tree
{
    int l0, r0, l1, r1, c0, c1, s0, s1, lz, rv;
} e[400005];

void merge(tree &x, tree y, tree z)
{
    x.s0 = y.s0 + z.s0;
    x.s1 = y.s1 + z.s1;
    x.c0 = max(max(y.c0, z.c0), y.r0 + z.l0);
    x.c1 = max(max(y.c1, z.c1), y.r1 + z.l1);
    x.l0 = (!y.s1) * z.l0 + y.l0;
    x.l1 = (!y.s0) * z.l1 + y.l1;
    x.r0 = (!z.s1) * y.r0 + z.r0;
    x.r1 = (!z.s0) * y.r1 + z.r1;
}

void pushup(int id)
{
    merge(e[id], e[lson], e[rson]);
}

void build(int l, int r, int id)
{
    e[id].lz = -1;
    if (l == r)
    {
        e[id].s0 = e[id].c0 = e[id].l0 = e[id].r0 = p[l] ^ 1;
        e[id].s1 = e[id].c1 = e[id].l1 = e[id].r1 = p[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, lson);
    build(mid + 1, r, rson);
    pushup(id);
}

void pushdown(int l, int r, int id)
{
    int mid = (l + r) >> 1, ls = mid - l + 1, rs = r - mid;
    if (e[id].lz == 0)
    {
        e[lson] = (tree){ls, ls, 0, 0, ls, 0, ls, 0, 0, 0};
        e[rson] = (tree){rs, rs, 0, 0, rs, 0, rs, 0, 0, 0};
    }
    else if (e[id].lz == 1)
    {
        e[lson] = (tree){0, 0, ls, ls, 0, ls, 0, ls, 1, 0};
        e[rson] = (tree){0, 0, rs, rs, 0, rs, 0, rs, 1, 0};
    }
    e[id].rv = ((~e[id].lz) ? 0 : e[id].rv);
    e[id].lz = -1;
    if (e[id].rv)
    {
        ((~e[lson].lz) ? (e[lson].lz ^= 1) : (e[lson].rv ^= 1));
        ((~e[rson].lz) ? (e[rson].lz ^= 1) : (e[lson].rv ^= 1));
        swap(e[lson].s0, e[lson].s1);
        swap(e[lson].l0, e[lson].l1);
        swap(e[lson].r0, e[lson].r1);
        swap(e[lson].c0, e[lson].c1);
        swap(e[rson].s0, e[rson].s1);
        swap(e[rson].l0, e[rson].l1);
        swap(e[rson].r0, e[rson].r1);
        swap(e[rson].c0, e[rson].c1);
    }
    e[id].rv = 0;
}

void change(int l, int r, int id, int x, int y, int op)
{

    pushdown(l, r, id);
    if (l >= x && r <= y)
    {
        if (op == 0)
        {
            e[id].lz = 0;
            e[id].l1 = e[id].r1 = e[id].s1 = e[id].c1 = 0;
            e[id].l0 = e[id].r0 = e[id].s0 = e[id].c0 = r - l + 1;
        }
        else if (op == 1)
        {
            e[id].lz = 1;
            e[id].l1 = e[id].r1 = e[id].s1 = e[id].c1 = r - l + 1;
            e[id].l0 = e[id].r0 = e[id].s0 = e[id].c0 = 0;
        }
        else
        {
            e[id].rv ^= 1;
            swap(e[id].s0, e[id].s1);
            swap(e[id].l0, e[id].l1);
            swap(e[id].r0, e[id].r1);
            swap(e[id].c0, e[id].c1);
        }
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
        change(l, mid, lson, x, y, op);
    if (y > mid)
        change(mid + 1, r, rson, x, y, op);
    pushup(id);
}

int qry1(int l, int r, int id, int x, int y)
{
    pushdown(l, r, id);
    if (l >= x && r <= y)
        return e[id].s1;
    int mid = (l + r) >> 1, ans = 0;
    if (x <= mid)
        ans += qry1(l, mid, lson, x, y);
    if (y > mid)
        ans += qry1(mid + 1, r, rson, x, y);
    return ans;
}

tree qry2(int l, int r, int id, int x, int y)
{
    pushdown(l, r, id);
    if (l >= x && r <= y)
        return e[id];
    int mid = (l + r) >> 1;
    if (mid >= y)
        return qry2(l, mid, lson, x, y);
    else if (mid < x)
        return qry2(mid + 1, r, rson, x, y);
    else
    {
        tree a = qry2(l, mid, lson, x, y),
             b = qry2(mid + 1, r, rson, x, y),
             ret;
        merge(ret, a, b);
        return ret;
    }
}

#undef lson
#undef rson
// sgt_end

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> p[i];
    build(1, n, 1);
    for (int i = 1, a, b, c; i <= m; i++)
    {
        cin >> a >> b >> c;
        b++, c++;
        if (a <= 2)
            change(1, n, 1, b, c, a);
        else if (a == 3)
            printf("%d\n", qry1(1, n, 1, b, c));
        else
            printf("%d\n", qry2(1, n, 1, b, c).c1);
    }
    return 0;
}

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

answer:
0
2
2

output:
0
1
0
*/

by 0000pnc @ 2023-05-05 22:31:30

((~e[rson].lz) ? (e[rson].lz ^= 1) : (e[lson].rv ^= 1));

草，此帖结

by ダ月 @ 2023-07-04 20:13:39

感谢这个 hack 数据/hsh

by zzZZzzZzzZzzzzzZzz @ 2023-07-13 22:34:25

感谢这个 hack 数据/hsh

by Zwb0106 @ 2023-08-04 23:15:03

感谢这个 hack 数据/hsh

by FL_sleake @ 2023-10-05 01:05:45

感谢这个 hack 数据/hsh