线段树WA10pts,求调

P2572 [SCOI2010] 序列操作

Sparse_Table @ 2024-12-11 17:26:19

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

int n, m;
int a[100005];

struct Tree {
    int l, r, lazytag, s0, s1, ls0, ls1, rs0, rs1, as0, as1; 
    // lazytag : 0 -> 无  1 -> 翻转  2 -> 0  3 -> 1 
} tr[100005 << 2];

void pushup(Tree &u, Tree l, Tree r) {
    u.s0 = l.s0 + r.s0;
    u.s1 = l.s1 + r.s1;
    u.ls0 = l.ls0;
    if (l.ls0 == l.r - l.l + 1)
        u.ls0 += r.ls0;
    u.rs0 = r.rs0;
    if (r.rs0 == r.r - r.l + 1)
        u.rs0 += l.rs0;
    u.ls1 = l.ls1;
    if (l.ls1 == l.r - l.l + 1)
        u.ls1 += r.ls1;
    u.rs1 = r.rs1;
    if (r.rs1 == r.r - r.l + 1)
        u.rs1 += l.rs1;
    u.as0 = max({ l.as0, r.as0, l.rs0 + r.ls0 });
    u.as1 = max({ l.as1, r.as1, l.rs1 + r.ls1 });
}

void tag(Tree &u, int op) {
    int len = u.r - u.l + 1;
    if (op == 0)
        u.as0 = u.ls0 = u.rs0 = u.s0 = len, u.as1 = u.ls1 = u.rs1 = u.s1 = 0, u.lazytag = 2;
    else if (op == 1)
        u.as0 = u.ls0 = u.rs0 = u.s0 = 0, u.as1 = u.ls1 = u.rs1 = u.s1 = len, u.lazytag = 3;
    else {
        swap(u.as0, u.as1);
        swap(u.ls0, u.ls1);
        swap(u.rs0, u.rs1);
        swap(u.s0, u.s1);
        u.lazytag ^= 1;
    }
}

void pushdown(Tree &u, Tree &l, Tree &r) {
    if (u.lazytag) {
        int llen = l.r - l.l + 1;
        int rlen = r.r - r.l + 1;
        l.lazytag = u.lazytag;
        r.lazytag = u.lazytag;
        if (u.lazytag == 1) {
            swap(l.as0, l.as1);
            swap(l.ls0, l.ls1);
            swap(l.rs0, l.rs1);
            swap(l.s0, l.s1);
            swap(r.as0, r.as1);
            swap(r.ls0, r.ls1);
            swap(r.rs0, r.rs1);
            swap(r.s0, r.s1);
        } else if (u.lazytag == 2) {
            l.as0 = l.ls0 = l.rs0 = l.s0 = llen, l.as1 = l.ls1 = l.rs1 = l.s1 = 0;
            r.as0 = r.ls0 = r.rs0 = r.s0 = rlen, r.as1 = r.ls1 = r.rs1 = r.s1 = 0;
        } else {
            l.as0 = l.ls0 = l.rs0 = l.s0 = 0, l.as1 = l.ls1 = l.rs1 = l.s1 = llen;
            r.as0 = r.ls0 = r.rs0 = r.s0 = 0, r.as1 = r.ls1 = r.rs1 = r.s1 = rlen;
        }
        u.lazytag = 0;
    }
}

void tag(int u, int op) {
    tag(tr[u], op);
}

void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void pushdown(int u) {
    pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = { l, r, 0, !a[l], a[l], !a[l], a[l], !a[l], a[l], !a[l], a[l] };
        return;
    }
    tr[u] = { l, r };
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int op) {
    if (l <= tr[u].l && tr[u].r <= r) {
        tag(u, op);
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
        modify(u << 1, l, r, op);
    if (r > mid)
        modify(u << 1 | 1, l, r, op);
    pushup(u);
}

Tree query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r)
        return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    Tree ans;
    if (r <= mid)
        return query(u << 1, l, r);
    else if (l > mid)
        return query(u << 1 | 1, l, r);
    else
        pushup(ans, query(u << 1, l, r), query(u << 1 | 1, l, r));
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i]; 
    build(1, 1, n);
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        x++, y++;
        switch (op) {
            case 0:
            case 1:
            case 2:
                modify(1, x, y, op);
                break;
            case 3:
                cout << query(1, x, y).s1 << "\n";
                break;
            case 4:
                cout << query(1, x, y).as1 << "\n";
                break;
            default:
                cout << "Error\n";
        }
    }
    return 0;
}

|