求调一下，hack过了，样例过了，但是0分

hyf_9134 @ 2024-10-28 16:45:56

#include <bits/stdc++.h>

#define int long long
#define all(x) (x).begin(), (x).end()
#define len(x) (x).size()
#define endl '\n'
#define lowbit(x) ((x) & -(x))

//using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int N = 1e5 + 10;
struct node {
    int l, r, len;
    int maxl0, maxr0, maxl1, maxr1, ans0, ans1, sum1, sum0;
    int or0, or1, tag;
};

std::vector<node> tree(N << 2);
std::vector<int> a(N);

void push_up(int root, int ls, int rs) {
    tree[root].maxl0 = tree[ls].maxl0;
    tree[root].maxl1 = tree[ls].maxl1;
    tree[root].maxr0 = tree[rs].maxr0;
    tree[root].maxr1 = tree[rs].maxr1;
    tree[root].sum0 = tree[ls].sum0 + tree[rs].sum0;
    tree[root].sum1 = tree[ls].sum1 + tree[rs].sum1;
    if (tree[ls].maxl0 == tree[ls].len) {
        tree[root].maxl0 += tree[rs].maxl0;
    }
    if (tree[ls].maxl1 == tree[ls].len) {
        tree[root].maxl1 += tree[rs].maxl1;
    }
    if (tree[rs].maxr0 == tree[rs].len) {
        tree[root].maxr0 += tree[ls].maxr0;
    }
    if (tree[rs].maxr1 == tree[rs].len) {
        tree[root].maxr1 += tree[ls].maxr1;
    }
    tree[root].ans0 = std::max({tree[ls].ans0, tree[rs].ans0, tree[ls].maxr0 + tree[rs].maxl0});
    tree[root].ans1 = std::max({tree[ls].ans1, tree[rs].ans1, tree[ls].maxr1 + tree[rs].maxl1});
}

void build(int root, int l, int r) {
    tree[root].l = l;
    tree[root].r = r;
    tree[root].len = (r - l + 1);
    if (l == r) {
        if (a[l]) {
            tree[root].maxl0 = 0;
            tree[root].maxr0 = 0;
            tree[root].maxl1 = 1;
            tree[root].maxr1 = 1;
            tree[root].ans1 = 1;
            tree[root].sum1 = 1;
            tree[root].ans0 = 0;
            tree[root].sum0 = 0;

        } else {
            tree[root].maxl0 = 1;
            tree[root].maxr0 = 1;
            tree[root].maxl1 = 0;
            tree[root].maxr1 = 0;
            tree[root].ans0 = 1;
            tree[root].sum0 = 1;
            tree[root].ans1 = 0;
            tree[root].sum1 = 0;
        }
        return;
    }
    int mid = (l + r) >> 1;
    int ls = root << 1;
    int rs = root << 1 | 1;

    build(ls, l, mid);
    build(rs, mid + 1, r);
    push_up(root, ls, rs);
}

void tag_change0(int root) {
    tree[root].or0 = 1;
    tree[root].or1 = 0;
    tree[root].tag = 0;
    tree[root].maxl0 = tree[root].len;
    tree[root].maxr0 = tree[root].len;
    tree[root].maxl1 = 0;
    tree[root].maxr1 = 0;
    tree[root].ans1 = 0;
    tree[root].ans0 = tree[root].len;
    tree[root].sum0 = tree[root].len;
    tree[root].sum1 = 0;
}

void tag_change1(int root) {
    tree[root].or0 = 0;
    tree[root].or1 = 1;
    tree[root].tag = 0;
    tree[root].maxl0 = 0;
    tree[root].maxr0 = 0;
    tree[root].maxl1 = tree[root].len;
    tree[root].maxr1 = tree[root].len;
    tree[root].ans1 = tree[root].len;
    tree[root].ans0 = 0;
    tree[root].sum0 = 0;
    tree[root].sum1 = tree[root].len;
}

void tag_change2(int root) {
    tree[root].or0 = 0;
    tree[root].or1 = 0;
    tree[root].tag = 1;
    std::swap(tree[root].ans0, tree[root].ans1);
    std::swap(tree[root].maxl1, tree[root].maxl0);
    std::swap(tree[root].maxr1, tree[root].maxr0);
    std::swap(tree[root].sum1, tree[root].sum0);
}

void push_down(int root, int ls, int rs) {
    if (tree[root].or0) {
        tag_change0(ls);
        tag_change0(rs);
    }
    if (tree[root].or1) {
        tag_change1(ls);
        tag_change1(rs);
    }
    if (tree[root].tag) {
        tag_change2(ls);
        tag_change2(rs);
    }
    tree[root].tag = tree[root].or0 = tree[root].or1 = 0;
}

void update(int root, int l, int r, int L, int R, int x) {
    if (L <= l && r <= R) {
        if (l != r) {
            int ls = root << 1;
            int rs = root << 1 | 1;
            push_down(root, ls, rs);
        }
        if (x == 0) {
            tag_change0(root);
        } else if (x == 1) {
            tag_change1(root);
        } else {
            tag_change2(root);
        }
        return;
    }

    int mid = (l + r) >> 1;
    int ls = root << 1;
    int rs = root << 1 | 1;
    push_down(root, ls, rs);
    if (L <= mid) {
        update(ls, l, mid, L, R, x);
    }
    if (R >= mid + 1) {
        update(rs, mid + 1, r, L, R, x);
    }
    push_up(root, ls, rs);
}

int query3(int root, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return tree[root].sum1;
    }
    int mid = (l + r) >> 1;
    int ls = root << 1;
    int rs = root << 1 | 1;
    int sum = 0;
    push_down(root, ls, rs);
    if (L <= mid) {
        sum += query3(ls, l, mid, L, R);
    }
    if (R >= mid + 1) {
        sum += query3(rs, mid + 1, r, L, R);
    }
    return sum;
}

node query4(int root, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return tree[root];
    }
    int mid = (l + r) >> 1;
    int ls = root << 1;
    int rs = root << 1 | 1;
    push_down(root, ls, rs);

    if (R <= mid) {
        return query4(ls, l, mid, L, R);
    } else if (L >= mid + 1) {
        return query4(rs, mid + 1, r, L, R);
    } else {
        node t, t1, t2;
        t1 = query4(ls, l, mid, L, R);
        t2 = query4(rs, mid + 1, r, L, R);
        t.l = t1.l;
        t.r = t2.r;
        t.len = t.r - t.l + 1;
        t.maxl0 = t1.maxl0;
        t.maxl1 = t1.maxl1;
        t.maxr0 = t2.maxr0;
        t.maxr1 = t2.maxr1;
        if (t1.maxl0 == t1.len) {
            t.maxl0 += t2.maxl0;
        }
        if (t1.maxl1 == t1.len) {
            t.maxl1 += t2.maxl1;
        }
        if (t2.maxr0 == t2.len) {
            t.maxr0 += t1.maxr0;
        }
        if (t2.maxr1 == t2.len) {
            t.maxr1 += t1.maxr1;
        }
        t.ans0 = std::max({t1.ans0, t2.ans0, t1.maxr0 + t2.maxl0});
        t.ans1 = std::max({t1.ans1, t2.ans1, t1.maxr1 + t2.maxl1});
        return t;
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    //std::cout.precision(10);
    int n, q;
    std::cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    build(1, 1, n);
    for (int i = 1; i <= q; i++) {
        int op, l, r;
        std::cin >> op >> l >> r;
        l++, r++;
        if (op <= 2) {
            update(1, 1, n, l, r, op);
        } else if (op == 3) {
            std::cout << query3(1, 1, n, l, r) << endl;
        } else {
            std::cout << query4(1, 1, n, l, r).ans1 << endl;
        }
    }

    return 0;
}

by xinglili @ 2024-10-31 16:50:31

可能是懒标记优先级或者懒标记重叠上的问题没有处理好？

by dtbigwaves @ 2024-11-01 16:02:26

dalao我和您一样 您过了吗

by hyf_9134 @ 2024-11-07 10:20:57

@dtbigwaves 已经过了我取反的懒标记错了

by hyf_9134 @ 2024-11-07 10:22:00

#include <bits/stdc++.h>

#define int long long
#define all(x) (x).begin(), (x).end()
#define len(x) (x).size()
#define endl '\n'
#define lowbit(x) ((x) & -(x))

//using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int N = 1e5 + 10;
struct node {
    int l, r, len;
    //管辖区间

    int maxl0, maxr0, maxl1, maxr1, ans0, ans1, sum1, sum0;
    //依次:
    //maxl0 从左边开始连续0最多 多少个
    //maxr0 从右边开始连续0最多 多少个

    //maxl1 从左边开始连续1最多 多少个
    //maxr1 从右边开始连续1最多 多少个

    //ans0 区间连续0最多 多少个
    //ans1 区间连续1最多 多少个

    //sum1 区间1 多少个
    //sum0 区间0 多少个

    int or0, or1, tag;
    //or0 全0标记
    //or1 全1标记
    //tag 取反
};

std::vector<node> tree(N << 2);
std::vector<int> a(N);

void push_up(int root, int ls, int rs) {
    tree[root].maxl0 = tree[ls].maxl0;
    tree[root].maxl1 = tree[ls].maxl1;
    tree[root].maxr0 = tree[rs].maxr0;
    tree[root].maxr1 = tree[rs].maxr1;
    tree[root].sum0 = tree[ls].sum0 + tree[rs].sum0;
    tree[root].sum1 = tree[ls].sum1 + tree[rs].sum1;
    if (tree[ls].maxl0 == tree[ls].len) {
        tree[root].maxl0 += tree[rs].maxl0;
    }
    if (tree[ls].maxl1 == tree[ls].len) {
        tree[root].maxl1 += tree[rs].maxl1;
    }
    if (tree[rs].maxr0 == tree[rs].len) {
        tree[root].maxr0 += tree[ls].maxr0;
    }
    if (tree[rs].maxr1 == tree[rs].len) {
        tree[root].maxr1 += tree[ls].maxr1;
    }
    tree[root].ans0 = std::max({tree[ls].ans0, tree[rs].ans0, tree[ls].maxr0 + tree[rs].maxl0});
    tree[root].ans1 = std::max({tree[ls].ans1, tree[rs].ans1, tree[ls].maxr1 + tree[rs].maxl1});
}

void build(int root, int l, int r) {
    tree[root].l = l;
    tree[root].r = r;
    tree[root].len = (r - l + 1);
    if (l == r) {
        if (a[l]) {
            tree[root].maxl0 = 0;
            tree[root].maxr0 = 0;
            tree[root].maxl1 = 1;
            tree[root].maxr1 = 1;
            tree[root].ans1 = 1;
            tree[root].sum1 = 1;
            tree[root].ans0 = 0;
            tree[root].sum0 = 0;

        } else {
            tree[root].maxl0 = 1;
            tree[root].maxr0 = 1;
            tree[root].maxl1 = 0;
            tree[root].maxr1 = 0;
            tree[root].ans0 = 1;
            tree[root].sum0 = 1;
            tree[root].ans1 = 0;
            tree[root].sum1 = 0;
        }
        return;
    }
    int mid = (l + r) >> 1;
    int ls = root << 1;
    int rs = root << 1 | 1;

    build(ls, l, mid);
    build(rs, mid + 1, r);
    push_up(root, ls, rs);
}

void tag_change0(int root) {
    tree[root].or0 = 1;
    tree[root].or1 = 0;
    tree[root].tag = 0;
    tree[root].maxl0 = tree[root].len;
    tree[root].maxr0 = tree[root].len;
    tree[root].maxl1 = 0;
    tree[root].maxr1 = 0;
    tree[root].ans1 = 0;
    tree[root].ans0 = tree[root].len;
    tree[root].sum0 = tree[root].len;
    tree[root].sum1 = 0;
}

void tag_change1(int root) {
    tree[root].or0 = 0;
    tree[root].or1 = 1;
    tree[root].tag = 0;
    tree[root].maxl0 = 0;
    tree[root].maxr0 = 0;
    tree[root].maxl1 = tree[root].len;
    tree[root].maxr1 = tree[root].len;
    tree[root].ans1 = tree[root].len;
    tree[root].ans0 = 0;
    tree[root].sum0 = 0;
    tree[root].sum1 = tree[root].len;
}

void tag_change2(int root) {
    tree[root].tag ^= 1;
    std::swap(tree[root].ans0, tree[root].ans1);
    std::swap(tree[root].maxl1, tree[root].maxl0);
    std::swap(tree[root].maxr1, tree[root].maxr0);
    std::swap(tree[root].sum1, tree[root].sum0);
}

void push_down(int root, int ls, int rs) {
    if (tree[root].or0) {
        tag_change0(ls);
        tag_change0(rs);
    }
    if (tree[root].or1) {
        tag_change1(ls);
        tag_change1(rs);
    }
    if (tree[root].tag) {
        tag_change2(ls);
        tag_change2(rs);
    }
    tree[root].tag = tree[root].or0 = tree[root].or1 = 0;
}

void update(int root, int l, int r, int L, int R, int x) {
    if (L <= l && r <= R) {
        if (x == 0) {
            tag_change0(root);
        } else if (x == 1) {
            tag_change1(root);
        } else {
            tag_change2(root);
        }
        return;
    }

    int mid = (l + r) >> 1;
    int ls = root << 1;
    int rs = root << 1 | 1;
    push_down(root, ls, rs);
    if (L <= mid) {
        update(ls, l, mid, L, R, x);
    }
    if (R >= mid + 1) {
        update(rs, mid + 1, r, L, R, x);
    }
    push_up(root, ls, rs);
} 

node query(int root, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return tree[root];
    }
    int mid = (l + r) >> 1;
    int ls = root << 1;
    int rs = root << 1 | 1;
    push_down(root, ls, rs);

    if (R <= mid) {
        return query(ls, l, mid, L, R);
    } else if (L >= mid + 1) {
        return query(rs, mid + 1, r, L, R);
    } else {
        node t, t1, t2;
        t1 = query(ls, l, mid, L, R);
        t2 = query(rs, mid + 1, r, L, R);
        t.l = t1.l;
        t.r = t2.r;
        t.len = t.r - t.l + 1;
        t.maxl0 = t1.maxl0;
        t.maxl1 = t1.maxl1;
        t.maxr0 = t2.maxr0;
        t.maxr1 = t2.maxr1;
        t.sum0 = t1.sum0 + t2.sum0;
        t.sum1 = t1.sum1 + t2.sum1;
        if (t1.maxl0 == t1.len) {
            t.maxl0 += t2.maxl0;
        }
        if (t1.maxl1 == t1.len) {
            t.maxl1 += t2.maxl1;
        }
        if (t2.maxr0 == t2.len) {
            t.maxr0 += t1.maxr0;
        }
        if (t2.maxr1 == t2.len) {
            t.maxr1 += t1.maxr1;
        }
        t.ans0 = std::max({t1.ans0, t2.ans0, t1.maxr0 + t2.maxl0});
        t.ans1 = std::max({t1.ans1, t2.ans1, t1.maxr1 + t2.maxl1});
        return t;
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    //std::cout.precision(10);
    int n, q;
    std::cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    build(1, 1, n);
    for (int i = 1; i <= q; i++) {
        int op, l, r;
        std::cin >> op >> l >> r;
        l++, r++;
        if (op <= 2) {
            update(1, 1, n, l, r, op);
        } else if (op == 3) {
            std::cout << query(1, 1, n, l, r).sum1 << endl;
        } else {
            std::cout << query(1, 1, n, l, r).ans1 << endl;
        }
    }

    return 0;
}

@dtbigwaves

by dtbigwaves @ 2024-11-07 11:35:29

@hyf_9134 https://www.luogu.com.cn/discuss/982306 大佬可以帮忙看下我取反懒标记有没有问题吗

实在找不到错

去翻懒标记是spread函数第51行