chenwenmo @ 2024-07-15 20:15:46
为什么在push_down时要先赋值再取反
by light_searcher @ 2024-07-15 20:24:20
@chenwenmo 喜欢你的头像
by kinghku_dzk @ 2024-07-15 20:36:24
@chenwenmo (qiqi
by Jim_Franklin @ 2024-07-15 20:43:08
@light_searcher +1
by dist_22r @ 2024-07-15 21:50:49
不是要先取反再赋值吗？！
by chenwenmo @ 2024-07-16 08:44:09
@dist_22r 不知道呀 我看了第一篇题解 说先赋值再取反 我不懂才来问
by dist_22r @ 2024-07-16 09:40:40
@chenwenmo 粉兔写的感觉有点抽象，你可以看一下第二篇和第四篇题解
by dist_22r @ 2024-07-16 09:42:00
@chenwenmo 如果先赋值可能会导致取反标记直接清空，所以要先反转，同时也反转了赋值标记
by dist_22r @ 2024-07-16 09:44:00
@chenwenmo 我这样写的
void push_down(int u,int l,int r)
{
int mid=(l+r)/2;
if(lazyf[u])//先取反
{
t[ls]=mid-l+1-t[ls];
swap(tl[ls][1],tl[ls][0]);
swap(tr[ls][1],tr[ls][0]);
swap(mt[ls][1],mt[ls][0]);
if(lazy[ls]!=-1)
{
lazy[ls]^=1;
}
lazyf[ls]^=1;
t[rs]=r-mid-t[rs];
swap(tl[rs][1],tl[rs][0]);
swap(tr[rs][1],tr[rs][0]);
swap(mt[rs][1],mt[rs][0]);
if(lazy[rs]!=-1)
{
lazy[rs]^=1;
}
lazyf[rs]^=1;
lazyf[u]=0;
}
if(lazy[u]!=-1)//再考虑赋值
{
lazy[ls]=lazy[u];
t[ls]=(mid-l+1)*lazy[u];
tl[ls][lazy[u]]=mid-l+1;
tr[ls][lazy[u]]=mid-l+1;
mt[ls][lazy[u]]=mid-l+1;
tl[ls][lazy[u]^1]=0;
tr[ls][lazy[u]^1]=0;
mt[ls][lazy[u]^1]=0;
lazyf[ls]=0;
lazy[rs]=lazy[u];
t[rs]=(r-mid)*lazy[u];
tl[rs][lazy[u]]=r-mid;
tr[rs][lazy[u]]=r-mid;
mt[rs][lazy[u]]=r-mid;
tl[rs][lazy[u]^1]=0;
tr[rs][lazy[u]^1]=0;
mt[rs][lazy[u]^1]=0;
lazyf[rs]=0;
lazy[u]=-1;
}
}by chenwenmo @ 2024-07-16 10:02:23
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N];
struct tree{
int len;
int l, r;
int t1, t2;//t1修改, t2取反
int s0, s1;
int m0, m1, l0, r0, l1, r1;
};
tree t[N * 4];
void push_up(int x){
tree l = t[x * 2], r = t[x * 2 + 1];
t[x].len = l.len + r.len;
t[x].s0 = l.s0 + r.s0;
t[x].s1 = l.s1 + r.s1;
t[x].l1 = l.s0 ? l.l1 : (l.s1 + r.l1);
t[x].r1 = r.s0 ? r.r1 : (r.s1 + l.r1);
t[x].l0 = l.s1 ? l.l0 : (l.s0 + r.l0);
t[x].r0 = r.s1 ? r.r0 : (r.s0 + l.r0);
t[x].m1 = max(l.m1, max(l.r1 + r.l1, r.m1));
t[x].m0 = max(l.m0, max(l.r0 + r.l0, r.m0));
}
void push_down(int x){
int l = x * 2, r = x * 2 + 1;
if(t[x].t1 == 0){
t[l].t1 = t[r].t1 = 0;
t[l].s1 = t[l].m1 = t[l].r1 = t[l].l1 = t[r].s1 = t[r].m1 = t[r].r1 = t[r].l1 = 0;
t[l].s0 = t[l].m0 = t[l].l0 = t[l].r0 = t[l].len;
t[r].s0 = t[r].m0 = t[r].l0 = t[r].r0 = t[r].len;
t[l].t2 = t[r].t2 = 0;
}
if(t[x].t1 == 1){
t[l].t1 = t[r].t1 = 1;
t[l].s0 = t[l].m0 = t[l].r0 = t[l].l0 = t[r].s0 = t[r].m0 = t[r].r0 = t[r].l0 = 0;
t[l].s1 = t[l].m1 = t[l].l1 = t[l].r1 = t[l].len;
t[r].s1 = t[r].m1 = t[r].l1 = t[r].r1 = t[r].len;
t[l].t2 = t[r].t2 = 0;
}
if(t[x].t2 == 1){
t[l].t2 ^= 1;
t[r].t2 ^= 1;
swap(t[l].s1, t[l].s0);
swap(t[l].m1, t[l].m0);
swap(t[l].l1, t[l].l0);
swap(t[l].r1, t[l].r0);
swap(t[r].s1, t[r].s0);
swap(t[r].m1, t[r].m0);
swap(t[r].l1, t[r].l0);
swap(t[r].r1, t[r].r0);
}
t[x].t1 = -1;
t[x].t2 = 0;
}
void build(int x, int l, int r){
t[x].l = l, t[x].r = r;
t[x].t1 = -1;
if(l == r){
t[x].len = 1;
t[x].m1 = t[x].s1 = t[x].l1 = t[x].r1 = a[l];
t[x].m0 = t[x].s0 = t[x].l0 = t[x].r0 = !a[l];
return;
}
int mid = l + r >> 1;
build(x * 2, l, mid);
build(x * 2 + 1, mid + 1, r);
push_up(x);
}
void update(int x, int l, int r, int op){
if(t[x].l >= l && t[x].r <= r){
if(op == 0){
t[x].t2 = 0;
t[x].t1 = 0;
t[x].s1 = t[x].m1 = t[x].r1 = t[x].l1 = 0;
t[x].s0 = t[x].m0 = t[x].l0 = t[x].r0 = t[x].len;
}else if(op == 1){
t[x].t2 = 0;
t[x].t1 = 1;
t[x].s1 = t[x].m1 = t[x].r1 = t[x].l1 = t[x].len;
t[x].s0 = t[x].m0 = t[x].l0 = t[x].r0 = 0;
}else{
t[x].t2 ^= 1;
swap(t[x].s1, t[x].s0);
swap(t[x].m1, t[x].m0);
swap(t[x].l1, t[x].l0);
swap(t[x].r1, t[x].r0);
}
return;
}
push_down(x);
int mid = t[x].l + t[x].r >> 1;
if(l <= mid) update(x * 2, l, r, op);
if(r > mid) update(x * 2 + 1, l, r, op);
push_up(x);
}
int query1(int x, int l, int r){
if(t[x].l >= l && t[x].r <= r){
return t[x].s1;
}
push_down(x);
int mid = t[x].l + t[x].r >> 1, ans = 0;
if(l <= mid) ans += query1(x * 2, l, r);
if(r > mid) ans += query1(x * 2 + 1, l, r);
return ans;
}
tree query2(int x, int l, int r){
if(t[x].l >= l && t[x].r <= r){
return t[x];
}
int mid = t[x].l + t[x].r >> 1;
push_down(x);
if(r <= mid) return query2(x * 2, l, r);
else if(l > mid) return query2(x * 2 + 1, l, r);
else{
tree ans, a = query2(x * 2, l, r), b = query2(x * 2 + 1, l, r);
ans.s0 = a.s0 + b.s0;
ans.s1 = a.s1 + b.s1;
ans.l1 = a.s0 ? a.l1 : (a.s1 + b.l1);
ans.r1 = b.s0 ? b.r1 : (b.s1 + a.r1);
ans.l0 = a.s1 ? a.l0 : (a.s0 + b.l0);
ans.r0 = b.s1 ? b.r0 : (b.s0 + a.r0);
ans.m1 = max(a.m1, max(a.r1 + b.l1, b.m1));
ans.m0 = max(a.m0, max(a.r0 + b.l0, b.m0));
return ans;
}
}
void check(int x, int l, int r){//调试用的
if(l == r){
cout << t[x].s1 << ' ';
return;
}
push_down(x);
int mid = l + r >> 1;
check(x * 2, l, mid);
check(x * 2 + 1, mid + 1, r);
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 0; i <= n - 1; i++){
scanf("%d", &a[i]);
}
build(1, 0, n - 1);
while(m--){
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
if(op < 3){
update(1, l, r, op);
}else if(op == 3){
int ans = query1(1, l, r);
printf("%d\n", ans);
}else{
tree ans = query2(1, l, r);
printf("%d\n", ans.m1);
}
//check(1, 0, n - 1);
//cout << endl;
}
return 0;
}by chenwenmo @ 2024-07-16 10:03:14
@dist_22r 改对了 这是ac代码 你看我push_down里面就是赋值再取反 换过来就错了 有点懵T_T