只有最后一个点过了,MnZn求调线段树

P2572 [SCOI2010] 序列操作

AK_heaven @ 2023-12-09 13:32:26

样例过了,hack数据也过了,但是全wa,求大佬指正错误,悬关。

#include <bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
struct Seg {
    int c, b;// num of 0, 1; 
    int l, r;// l, r;
    int lb, lc, rb, rc, mb, mc;// left 1, left 0, right 1, right 0, max 1, max 0;
    int tag, rev, len;// op = 1, 2; op = 3; length of range 
}tr[maxn<<2];

void pushup(Seg &T, Seg L, Seg R) {
    T.b = L.b+R.b;
    T.c = L.c+R.c;
    T.lb = L.c ? L.lb : L.lb+R.lb; // 如果左边全是1,那么就是左边全部加右边的左边的1 
    T.lc = L.b ? L.lc : L.lc+R.lc; // 同理 
    T.rb = R.c ? R.lb : R.lb+L.lb;
    T.rc = R.b ? R.lc : R.lc+L.lc;
    T.mb = max(max(L.mb, R.mb), L.rb + R.lb);
    T.mc = max(max(L.mc, R.mc), L.rc + R.lc);
}

void calc(int p, int op) {
    Seg& t = tr[p];
    if(op == 0) {
        t.b = t.lb = t.mb = t.rb = 0;
        t.c = t.lc = t.rc = t.mc = t.len;
        t.tag = 0, t.rev = 0;
    }
    else if(op == 1) {
        t.b = t.lb = t.mb = t.rb = t.len;
        t.c = t.lc = t.rc = t.mc = 0;
        t.tag = 1, t.rev = 0;
    }
    else {
        swap(t.b, t.c); swap(t.lb, t.lc);
        swap(t.mb, t.mc); swap(t.rb, t.rc);
        t.rev ^= 1; 
    }
}

void pushdown(int p) {
    if(tr[p].tag == 0) {
        calc(ls, 0);
        calc(rs, 0);
    }
    if(tr[p].tag == 1) {
        calc(ls, 1);
        calc(rs, 1);
    }
    if(tr[p].rev) {
        calc(ls, 2);
        calc(rs, 2);
    }   
    tr[p].tag = -1;
    tr[p].rev = 0;
}

void build(int p, int l, int r) {
    tr[p].l = l, tr[p].r = r;
    tr[p].tag = -1; tr[p].len = r-l+1;
    if(l == r) {
        if(a[l]) tr[p].b = tr[p].lb = tr[p].mb = tr[p].rb = 1;
        else tr[p].c = tr[p].lc = tr[p].mc = tr[p].rc = 1;
        return ;
    }
    int mid = (l+r)/2;
    build(ls, l, mid);
    build(rs, mid+1, r);
    pushup(tr[p], tr[ls], tr[rs]);
}

void update(int p, int x, int y, int k) {
    if(x > tr[p].r || y < tr[p].l) return ; 
    if(x <= tr[p].l && tr[p].r <= y) {
        calc(p, k);
//      if(k == 0 || k == 1)
//          tr[p].tag = k;
//      else tr[p].rev ^= 1;
        return ;
    }
    int mid = (tr[p].l + tr[p].r)/2;
    pushdown(p);
    if(x <= mid) update(ls, x, y, k);
    if(y > mid) update(rs, x, y, k);
    pushup(tr[p], tr[ls], tr[rs]);
}

Seg query(int p, int x, int y) {
    if(x > tr[p].r || y < tr[p].l) return {};
    if(x <= tr[p].l && tr[p].r <= y) {
        return tr[p];
    }
    pushdown(p);
    Seg T;
    pushup(T, query(ls, x, y), query(rs, x, y));
    return T;
}
int n, m;
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
      cin >> a[i];
    build(1, 1, n);
    for(int i = 1, op, x, y; i <= m; i++) {
        cin >> op >> x >> y;
        x++, y++;
        if(op < 3) {
            update(1, x, y, op);
        }
        else if(op == 3) {
            cout << query(1, x, y).b << '\n';
        }
        else cout << query(1, x, y).mb << '\n';
    }
    return 0;
}

by _Paradox_ @ 2023-12-09 14:03:25

鉴定为pushup写错了

void pushup(Seg &T, Seg L, Seg R) {
    T.b = L.b+R.b;
    T.c = L.c+R.c;
    T.lb = L.lb == L.r-L.l+1 ? L.lb + R.lb : L.lb;
    T.lc = L.lc == L.r-L.l+1 ? L.lc + R.lc : L.lc;
    T.rb = R.rb == R.r-R.l+1 ? R.rb + L.rb : R.rb;
    T.rc = R.rc == R.r-R.l+1 ? R.rc + L.rc : R.rc;
    T.mb = max(max(L.mb, R.mb), L.rb + R.lb);
    T.mc = max(max(L.mc, R.mc), L.rc + R.lc);
}

by _Paradox_ @ 2023-12-09 14:03:56

把这里改了就a了


by _Paradox_ @ 2023-12-09 14:04:53

@AK_heaven


by AK_heaven @ 2023-12-09 16:35:32

@Paradox 谢谢,已关注


|