小萌新求调简单清新好写板子线段树

P2572 [SCOI2010] 序列操作

1234567890sjx @ 2024-07-06 22:48:28


bool begmem;
#include <bits/stdc++.h>
#define int long long
using namespace std;
class FastIO {
public:
    int read() {
        int o = 1, x; char ch;
        while (!isdigit(ch = getchar())) {
            if (ch == '-') {
                o = -1;
            }
        }
        x = ch ^ 48;
        while (isdigit(ch = getchar())) {
            x = (x << 3) + (x << 1) + (ch ^ 48);
        }
        return o * x;
    }
} ; FastIO io;

void calcqwq();
const int N = 100100, inf = 1e18;
int a[N];
inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a < b ? a : b; }
inline void swap(int &a, int &b) { a ^= b ^= a ^= b; }
struct Node {
    int l, r, sum0, sum1, zuo0, zuo1, you0, you1, mx0, mx1, rev, tag;
    void init(int p) {
        l = r = p, rev = 0, tag = -1;
        if (a[p] == 0) {
            sum0 = 1, sum1 = 0;
            zuo0 = 1, zuo1 = 0;
            you0 = 1, you1 = 0;
            mx0 = 1, mx1 = 0;
        } else {
            sum0 = 0, sum1 = 1;
            zuo0 = 0, zuo1 = 1;
            you0 = 0, you1 = 1;
            mx0 = 0, mx1 = 1;
        }
    }
} z[N << 2];
Node operator+(const Node &l, const Node &r) {
    Node res;
    res.l = l.l, res.r = r.r, res.rev = 0, res.tag = -1;
    res.sum0 = l.sum0 + r.sum0, res.sum1 = l.sum1 + r.sum1;
    res.mx0 = max({l.mx0, r.mx0, l.you0 + r.zuo0});
    res.mx1 = max({l.mx1, r.mx1, l.you1 + r.zuo1});
    if (l.r - l.l + 1 == l.zuo0) res.zuo0 = l.r - l.l + 1 + r.zuo0;
    if (l.r - l.l + 1 == l.zuo1) res.zuo1 = l.r - l.l + 1 + r.zuo1;
    if (r.r - r.l + 1 == r.you0) res.you0 = r.r - r.l + 1 + r.you0;
    if (r.r - r.l + 1 == r.you1) res.you1 = r.r - r.l + 1 + r.you1;
    return res;
}
void build(int l, int r, int rt) {
    if (l == r) return z[rt].init(l);
    int mid = l + r >> 1;
    build(l, mid, rt << 1), build(mid + 1, r, rt << 1 | 1);
    z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
void push_down(int rt) {
    if (~z[rt].tag) {
        z[rt << 1].tag = z[rt << 1 | 1].tag = z[rt].tag;
        z[rt].rev = 0;
        if (z[rt << 1].tag == 0) {
            z[rt << 1].sum0 = z[rt << 1].r - z[rt << 1].l + 1;
            z[rt << 1].mx0 = z[rt << 1].r - z[rt << 1].l + 1;
            z[rt << 1].zuo0 = z[rt << 1].r - z[rt << 1].l + 1;
            z[rt << 1].you0 = z[rt << 1].r - z[rt << 1].l + 1;
            z[rt << 1].sum1 = z[rt << 1].mx1 = z[rt << 1].zuo1 = z[rt << 1].you1 = 0;
        } else {
            z[rt << 1].sum1 = z[rt << 1].r - z[rt << 1].l + 1;
            z[rt << 1].mx1 = z[rt << 1].r - z[rt << 1].l + 1;
            z[rt << 1].zuo1 = z[rt << 1].r - z[rt << 1].l + 1;
            z[rt << 1].you1 = z[rt << 1].r - z[rt << 1].l + 1;
            z[rt << 1].sum0 = z[rt << 1].mx0 = z[rt << 1].zuo0 = z[rt << 1].you0 = 0;
        }
        if (z[rt << 1 | 1].tag == 0) {
            z[rt << 1 | 1].sum0 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
            z[rt << 1 | 1].mx0 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
            z[rt << 1 | 1].zuo0 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
            z[rt << 1 | 1].you0 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
            z[rt << 1 | 1].sum1 = z[rt << 1 | 1].mx1 = z[rt << 1 | 1].zuo1 = z[rt << 1 | 1].you1 = 0;
        } else {
            z[rt << 1 | 1].sum1 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
            z[rt << 1 | 1].mx1 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
            z[rt << 1 | 1].zuo1 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
            z[rt << 1 | 1].you1 = z[rt << 1 | 1].r - z[rt << 1 | 1].l + 1;
            z[rt << 1 | 1].sum0 = z[rt << 1 | 1].mx0 = z[rt << 1 | 1].zuo0 = z[rt << 1 | 1].you0 = 0;
        }
        z[rt].tag = -1;
    }
    if (z[rt].rev) {
        z[rt].rev = 0;
        z[rt << 1].rev ^= 1, z[rt << 1 | 1].rev ^= 1;
        if (z[rt << 1].rev) {
            swap(z[rt << 1].zuo1, z[rt << 1].zuo0);
            swap(z[rt << 1].you1, z[rt << 1].you0);
            swap(z[rt << 1].mx0, z[rt << 1].mx1);
            swap(z[rt << 1].sum0, z[rt << 1].sum1);
        }
        if (z[rt << 1 | 1].rev) {
            swap(z[rt << 1 | 1].zuo1, z[rt << 1 | 1].zuo0);
            swap(z[rt << 1 | 1].you1, z[rt << 1 | 1].you0);
            swap(z[rt << 1 | 1].mx0, z[rt << 1 | 1].mx1);
            swap(z[rt << 1 | 1].sum0, z[rt << 1 | 1].sum1);
        }
    }
}
void modify1(int l, int r, int rt, int ll, int rr, int v) {
    if (ll <= l && r <= rr) {
        if (v == 1) {
            z[rt].sum0 = z[rt].mx0 = z[rt].zuo0 = z[rt].you0 = 0;
            z[rt].sum1 = z[rt].r - z[rt].l + 1;
            z[rt].mx1 = z[rt].r - z[rt].l + 1;
            z[rt].zuo1 = z[rt].r - z[rt].l + 1;
            z[rt].you1 = z[rt].r - z[rt].l + 1;
        } else {
            z[rt].sum1 = z[rt].mx1 = z[rt].zuo1 = z[rt].you1 = 0;
            z[rt].sum0 = z[rt].r - z[rt].l + 1;
            z[rt].mx0 = z[rt].r - z[rt].l + 1;
            z[rt].zuo0 = z[rt].r - z[rt].l + 1;
            z[rt].you0 = z[rt].r - z[rt].l + 1;
        }
        return;
    }
    int mid = l + r >> 1;
    push_down(rt);
    if (ll <= mid) modify1(l, mid, rt << 1, ll, rr, v);
    if (mid < rr) modify1(mid + 1, r, rt << 1 | 1, ll, rr, v);
    z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
void modify2(int l, int r, int rt, int ll, int rr) {
    if (ll <= l && r <= rr) {
        swap(z[rt].zuo1, z[rt].zuo0);
        swap(z[rt].you1, z[rt].you0);
        swap(z[rt].mx0, z[rt].mx1);
        swap(z[rt].sum0, z[rt].sum1);
        return;
    }
    int mid = l + r >> 1;
    push_down(rt);
    if (ll <= mid) modify2(l, mid, rt << 1, ll, rr);
    if (mid < rr) modify2(mid + 1, r, rt << 1 | 1, ll, rr);
    z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
Node query(int l, int r, int rt, int ll, int rr) {
    if (ll <= l && r <= rr) return z[rt];
    int mid = l + r >> 1;
    push_down(rt);
    if (ll <= mid && mid < rr) return query(l, mid, rt << 1, ll, rr) + query(mid + 1, r, rt << 1 | 1, ll, rr);
    if (ll <= mid) return query(l, mid, rt << 1, ll, rr);
    return query(mid + 1, r, rt << 1 | 1, ll, rr);
}
signed main() {
    atexit(calcqwq);
    int n = io.read(), m = io.read();
    for (int i = 1; i <= n; ++i) a[i] = io.read();
    build(1, n, 1);
    while (m--) {
        int o = io.read(), l = io.read(), r = io.read();
        l++, r++;
        if (o <= 1) modify1(1, n, 1, l, r, o);
        else if (o == 2) modify2(1, n, 1, l, r);
        else if (o == 3) printf("%lld\n", query(1, n, 1, l, r).sum1);
        else printf("%lld\n", query(1, n, 1, l, r).mx1);
    }
}
bool endmem;
void calcqwq() {
    fprintf(stderr, "Memory = %.5lf\n", (&begmem - &endmem) / 1048576.);
}

|