调了很久了,求DALAO帮助

P2572 [SCOI2010] 序列操作

Midnight_szx @ 2024-01-24 15:34:08

rt,悬一关

#include<bits/stdc++.h>
using namespace std;
struct node{
    int sum, ml, mr, ans, ans0, sum0;//s和,ml左最长1,mr右最长1,ans最多连续的1,ans0最多连续的0 
    int l0, r0;//左右最长0 
    int tag1;//取反 
    int tag2;
}t[400005];
int a[100005], n, m;
int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }
void pushup(int p) {
    t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
    t[p].sum0 = t[ls(p)].sum0 + t[rs(p)].sum0;
    t[p].ans = max(max(t[ls(p)].ans, t[rs(p)].ans), t[ls(p)].mr + t[rs(p)].ml);
    t[p].ans0 = max(max(t[ls(p)].ans0, t[rs(p)].ans0), t[ls(p)].r0 + t[rs(p)].l0);

    t[p].ml = (t[ls(p)].sum == t[ls(p)].ml) ? t[ls(p)].sum + t[rs(p)].ml : t[ls(p)].ml;
    t[p].mr = (t[rs(p)].sum == t[rs(p)].mr) ? t[rs(p)].sum + t[ls(p)].mr : t[rs(p)].mr;
    t[p].l0 = (t[ls(p)].l0 == t[ls(p)].sum0) ? t[ls(p)].sum0 + t[rs(p)].l0 : t[ls(p)].l0;
    t[p].r0 = (t[rs(p)].r0 == t[rs(p)].sum0) ? t[rs(p)].sum0 + t[ls(p)].r0 : t[rs(p)].r0;

}
void pushdown(int l, int r, int p) {
    int mid = l + r >> 1;
    if(t[p].tag1) {
        swap(t[ls(p)].ml, t[ls(p)].l0);
        swap(t[ls(p)].mr, t[ls(p)].r0);
        swap(t[ls(p)].sum, t[ls(p)].sum0);
        swap(t[ls(p)].ans, t[ls(p)].ans0);

        swap(t[rs(p)].ml, t[rs(p)].l0);
        swap(t[rs(p)].mr, t[rs(p)].r0);
        swap(t[rs(p)].sum0, t[rs(p)].sum);
        swap(t[rs(p)].ans, t[rs(p)].ans0);

        t[p].tag1 = 0;
        t[ls(p)].tag1 ^= 1;
        t[rs(p)].tag1 ^= 1;
    }
    if(t[p].tag2 == 0) {
        t[ls(p)].ans = t[ls(p)].sum = t[ls(p)].ml = t[ls(p)].mr = 0;
        t[rs(p)].ans = t[rs(p)].sum = t[rs(p)].ml = t[rs(p)].mr = 0;
        t[ls(p)].ans0 = t[ls(p)].sum0 = t[ls(p)].l0 = t[ls(p)].r0 = mid - l + 1;
        t[rs(p)].ans0 = t[rs(p)].sum0 = t[rs(p)].l0 = t[rs(p)].r0 = r - mid;

        t[p].tag2 = -1;
        t[ls(p)].tag2 = t[rs(p)].tag2 = -1;
    }
    if(t[p].tag2 == 1) {
        t[ls(p)].ans0 = t[ls(p)].sum0 = t[ls(p)].l0 = t[ls(p)].r0 = 0;
        t[rs(p)].ans0 = t[rs(p)].sum0 = t[rs(p)].l0 = t[rs(p)].r0 = 0;
        t[ls(p)].ans = t[ls(p)].sum = t[ls(p)].ml = t[ls(p)].mr = mid - l + 1;
        t[rs(p)].ans = t[rs(p)].sum = t[rs(p)].ml = t[rs(p)].mr = r - mid;

        t[p].tag2 = -1;
        t[ls(p)].tag2 = t[rs(p)].tag2 = -1;
    }
}
void build(int l, int r, int p) {
    t[p].tag1 = 0;
    t[p].tag2 = -1;
    if(l == r) { 
        t[p].sum = a[l];
        t[p].sum0 = !a[l];
        t[p].ml = t[p].mr = t[p].ans = a[l];
        t[p].l0 = t[p].r0 = t[p].ans0 = !a[l];
        return;
    } 
    int mid = l + r >> 1;
    build(l, mid, ls(p));
    build(mid + 1, r, rs(p));
    pushup(p);
}
void turn_0(int sl, int sr, int l, int r, int p) {
    if(sl <= l and r <= sr) {
        t[p].sum = 0;
        t[p].ans = 0;
        t[p].ans0 = t[p].sum0 = r - l + 1;
        t[p].ml = t[p].mr = 0;
        t[p].l0 = t[p].r0 = r - l + 1;
        t[p].tag2 = 0;
        return;
    }
    pushdown(l, r, p);
    int mid = l + r >> 1;
    if(mid >= sl) turn_0(sl, sr, l, mid,ls(p));
    if(mid < sr) turn_0(sl, sr, mid + 1, r, rs(p));
    pushup(p);
}
void turn_1(int sl, int sr, int l, int r, int p) {
    if(sl <= l and r <= sr) {
        t[p].sum = r - l + 1;
        t[p].ans = r - l + 1;
        t[p].ans0 = 0;
        t[p].sum0 = 0;
        t[p].ml = t[p].mr = r - l + 1;
        t[p].l0 = t[p].r0 = 0;
        t[p].tag1 = 1;
        return;
    }
    pushdown(l, r, p);
    int mid = l + r >> 1;
    if(mid >= sl) turn_1(sl, sr, l, mid,ls(p));
    if(mid < sr) turn_1(sl, sr, mid + 1, r, rs(p));
    pushup(p);
}
void trans(int sl, int sr, int l, int r, int p) {
    if(sl <= l and r <= sr) {
        t[p].tag1 = t[p].tag1 ^ 1;
        swap(t[p].ml, t[p].l0);
        swap(t[p].mr, t[p].r0);
        swap(t[p].sum, t[p].sum0);
        swap(t[p].ans, t[p].ans0);
        return;
    }
    pushdown(l, r, p);
    int mid = l + r >> 1;
    if(mid >= sl) trans(sl, sr, l, mid,ls(p));
    if(mid < sr) trans(sl, sr, mid + 1, r, rs(p));
    pushup(p);
}
int query_sum(int sl, int sr, int l, int r, int p) {
    if(sl <= l and r <= sr) 
        return t[p].sum;
    pushdown(l, r, p);
    int mid = l + r >> 1, k = 0;
    if(mid >= sl) k += query_sum(sl, sr, l, mid, ls(p));
    if(mid < sr) k += query_sum(sl, sr, mid + 1, r, rs(p));
    return k;
}
node query(int sl, int sr, int l, int r, int p) {
    if(sl <= l and r <= sr) 
        return t[p];
    if(l > sr or r < sl) return (node){0};
    pushdown(l, r, p);
    int mid = l + r >> 1;
    node ll = query(sl, sr, l, mid, ls(p)), rr = query(sl, sr, mid + 1, r, rs(p)), k;
    k.sum = ll.sum + rr.sum;
    k.ans = max(ll.ans, rr.ans);
    k.ans0 = max(ll.ans0, rr.ans0);
    k.ml = (mid - l + 1 == ll.sum) ? ll.sum + rr.ml : ll.ml;
    k.mr = (r - mid == rr.sum) ? rr.sum + ll.mr : rr.mr;
    k.l0 = (mid - l + 1 == ll.sum0) ? ll.sum0 + rr.l0 : ll.l0;
    k.r0 = (r - mid == rr.sum0) ? rr.sum0 + ll.r0 : rr.r0;
    k.ans = max(k.ans, ll.mr + rr.ml);
    k.ans0 = max(k.ans0, ll.r0 + rr.l0);
    return k;
}
int main() {
    cin>>n>>m;
    for(int i = 1; i <= n; i++) 
        cin>>a[i];
    build(1, n, 1);
    int op, l, r;
    while(m--) {
        cin>>op;
        cin>>l>>r;
        if(op == 0) 
            turn_0(l, r, 1, n, 1);
        if(op == 1) 
            turn_1(l, r, 1, n, 1);
        if(op == 2) 
            trans(l, r, 1, n, 1);
        if(op == 3) 
            cout<<query_sum(l, r, 1, n, 1)<<'\n';
        if(op == 4) 
            cout<<query(l, r, 1, n, 1).ans<<'\n';
    }
    return 0;
}

by Midnight_szx @ 2024-01-24 15:35:42

似乎是 query 写错了pwp


by call_of_silence @ 2024-01-24 15:38:19

@Midnight_szx

建议把所有需要合并的地方写成一个merge函数,这样太难调了


by Midnight_szx @ 2024-01-24 15:39:16

@call_of_silence 谔谔但是那样写的不习惯pwp


|