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 谢谢,已关注