求调,实在找不到bug

P2572 [SCOI2010] 序列操作

zxh_mc @ 2022-10-19 20:54:53

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m, a[N];

struct val {
    int lm, rm, m, mk, l, r;
};

struct node {
    int l, r, lmo, rmo, num, flag, mz, mo, lmz, rmz;     //flag = 1: 全0    flag = 2: 全1     flag = 3:全反 
}tree[N * 4];

inline void update (int p, int op) {
    tree[p].flag = op;
    if (op == 1) {
        tree[p].num = tree[p].lmo = tree[p].rmo = tree[p].mo = 0;
        tree[p].lmz = tree[p].rmz = tree[p].mz = tree[p].r - tree[p].l + 1;
    }
    else if (op == 2) {
        tree[p].num = tree[p].lmo = tree[p].rmo = tree[p].mo = tree[p].r - tree[p].l + 1;
        tree[p].lmz = tree[p].rmz = tree[p].mz = 0;
    }
    else if (op == 3) {
        swap(tree[p].lmo, tree[p].lmz);
        swap(tree[p].rmo, tree[p].rmz);
        swap(tree[p].mo, tree[p].mz);
        tree[p].num = tree[p].r - tree[p].l + 1 - tree[p].num;
    }
}

inline void push_up(int p) {
    tree[p].num = tree[p * 2].num + tree[p * 2 + 1].num;
    tree[p].mo = max(max(tree[p * 2].mo, tree[p * 2 + 1].mo), tree[p * 2].lmo + tree[p * 2 + 1].rmo);
    tree[p].mz = max(max(tree[p * 2].mz, tree[p * 2 + 1].mz), tree[p * 2].lmz + tree[p * 2 + 1].rmz);

    if (tree[p * 2].rmo < tree[p * 2].r - tree[p * 2].l + 1) tree[p].rmo = tree[p * 2].rmo;
    else tree[p].rmo = tree[p * 2].rmo + tree[p * 2 + 1].rmo;
    if (tree[p * 2 + 1].lmo < tree[p * 2 + 1].r - tree[p * 2 + 1].l + 1) tree[p].lmo = tree[p * 2 + 1].lmo;
    else tree[p].lmo = tree[p * 2 + 1].lmo + tree[p * 2].lmo;

    if (tree[p * 2].rmz < tree[p * 2].r - tree[p * 2].l + 1) tree[p].rmz = tree[p * 2].rmz;
    else tree[p].rmz = tree[p * 2].rmz + tree[p * 2 + 1].rmz;
    if (tree[p * 2 + 1].lmz < tree[p * 2 + 1].r - tree[p * 2 + 1].l + 1) tree[p].lmz = tree[p * 2 + 1].lmz;
    else tree[p].lmz = tree[p * 2 + 1].lmz + tree[p * 2].lmz;

}

inline void push_down(int p) {
    update(p * 2, tree[p].flag); update(p * 2 + 1, tree[p].flag);
    tree[p].flag = 0;
}

void build (int p, int l, int r) {
    tree[p].l = l, tree[p].r = r;
    if (l == r) {
        if (a[l]) tree[p].lmo = tree[p].rmo = tree[p].mo = tree[p].num = 1;
        else tree[p].lmz = tree[p].rmz = tree[p].mz = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if (l <= mid) build(p * 2, l, mid);
    if (r > mid) build(p * 2 + 1, mid + 1, r);
    push_up(p);
}

void add (int p, int l, int r, int op) {
    int tl = tree[p].l, tr = tree[p].r;
    if (tree[p].flag) push_down(p);
    if (tl >= l && tr <= r) {
        update(p, op);
        return;
    }
    int mid = (tl + tr) >> 1;
    if (l <= mid) add(p * 2, l, r, op);
    if (r > mid) add(p * 2 + 1, l, r, op);
    push_up(p);
}

int qp4 (int p, int l, int r) {
    int tl = tree[p].l, tr = tree[p].r;
    if (tree[p].flag) push_down(p);
    if (tl >= l && tr <= r) return tree[p].num;
    int mid = (tl + tr) >> 1, res = 0;
    if (l <= mid) res += qp4(p * 2, l, r);
    if (r > mid) res += qp4(p * 2 + 1, l, r);
    return res;
}

val qp5 (int p, int l, int r) {
    int tl = tree[p].l, tr = tree[p].r, lm = tree[p].lmo, rm = tree[p].rmo, m = tree[p].mo;
    if (tree[p].flag) push_down(p);
    if (tl >= l && tr <= r) return (val){lm, rm, m, 1, tl, tr};
    int mid = (tl + tr) >> 1;
    val a, b, c;
    a = b = c = (val){0, 0, 0, 0, 0, 0};
    c.mk = 1;
    if (l <= mid) a = qp5(p * 2, l, r);
    if (r > mid) b = qp5(p * 2 + 1, l, r);
    if (!b.mk) return a;
    if (!a.mk) return b;
    c.m = max(max(a.m, b.m), a.lm + b.rm);
    if (a.rm < a.r - a.l + 1) c.rm = a.rm;
    else c.rm = a.rm + b.rm;
    if (b.lm < b.r - b.l + 1) c.lm = b.lm;
    else c.lm = b.lm + a.lm;
    c.l = a.l, c.r = b.r;
    return c;
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= n;i++) scanf("%d", &a[i]);
    build(1, 1, n);
    while (m--) {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        l++;r++;
        if (op <= 2) add(1, l, r, op + 1);
        else if (op == 3) printf("%d\n", qp4(1, l, r));
        else printf("%d\n", qp5(1, l, r).m);
    }
    return 0;
}

感觉思路没错,调出来几个bug还是不过


by xingke233 @ 2022-10-19 20:59:47

@zxh_minecraft

找不到bug,就重构

这题我之前调了一下午才调出来


by zxh_mc @ 2022-10-20 12:33:38

已经A力


|