Lian_zy @ 2024-12-14 21:39:46
rt,找了好久错了,还是不知道错在哪
Subtask#1的一个点AC了
#include<bits/stdc++.h>
#define N 100005
using namespace std;
//区间变0/1 ->tag
//区间取反 ->puttag
//区间和 ->sum0/sum1
//区间最长连续1 ->ans0,ans1,rmx0,rmx1,lmx0,lmx1
struct node{
int l,r;
int sum0,sum1;
int ans0,ans1,rmx0,rmx1,lmx0,lmx1;
int tag,puttag;
}none,t[N<<2];
int n,m,x,y,z,a[N];
node push_up(node ans,node ls,node rs){
ans.sum0=ls.sum0+rs.sum0;
ans.sum1=ls.sum1+rs.sum1;
//从左/右起最长的连续0/1
//left
ans.lmx0=ls.lmx0+(ls.lmx0==ls.r-ls.l+1)*rs.lmx0;
ans.lmx1=ls.lmx1+(ls.lmx1==ls.r-ls.l+1)*rs.lmx1;
//right
ans.rmx0=rs.rmx0+(rs.rmx0==rs.r-rs.l+1)*ls.rmx0;
ans.rmx1=rs.rmx1+(rs.rmx1==rs.r-rs.l+1)*ls.rmx1;
//获取ans
ans.ans0=max(max(ls.ans0,rs.ans0),ls.rmx0+rs.lmx0);
ans.ans1=max(max(ls.ans1,rs.ans1),ls.rmx1+rs.lmx1);
return ans;
}
void push_down(int x){
//先赋值再取反
if(~t[x].puttag){//处理区间赋值标记
if(t[x].puttag){//标记:区间赋1
t[x<<1].ans0=0;
t[x<<1].lmx0=0;
t[x<<1].rmx0=0;
t[x<<1].sum0=0;
t[x<<1].ans1=t[x<<1].r-t[x<<1].l+1;
t[x<<1].lmx1=t[x<<1].r-t[x<<1].l+1;
t[x<<1].rmx1=t[x<<1].r-t[x<<1].l+1;
t[x<<1].sum1=t[x<<1].r-t[x<<1].l+1;
t[x<<1|1].ans0=0;
t[x<<1|1].lmx0=0;
t[x<<1|1].rmx0=0;
t[x<<1|1].sum0=0;
t[x<<1|1].ans1=t[x<<1|1].r-t[x<<1|1].l+1;
t[x<<1|1].lmx1=t[x<<1|1].r-t[x<<1|1].l+1;
t[x<<1|1].rmx1=t[x<<1|1].r-t[x<<1|1].l+1;
t[x<<1|1].sum1=t[x<<1|1].r-t[x<<1|1].l+1;
}else{//区间赋0
t[x<<1].ans1=0;
t[x<<1].lmx1=0;
t[x<<1].rmx1=0;
t[x<<1].sum1=0;
t[x<<1].ans0=t[x<<1].r-t[x<<1].l+1;
t[x<<1].lmx0=t[x<<1].r-t[x<<1].l+1;
t[x<<1].rmx0=t[x<<1].r-t[x<<1].l+1;
t[x<<1].sum0=t[x<<1].r-t[x<<1].l+1;
t[x<<1|1].ans1=0;
t[x<<1|1].lmx1=0;
t[x<<1|1].rmx1=0;
t[x<<1|1].sum1=0;
t[x<<1|1].ans0=t[x<<1|1].r-t[x<<1|1].l+1;
t[x<<1|1].lmx0=t[x<<1|1].r-t[x<<1|1].l+1;
t[x<<1|1].rmx0=t[x<<1|1].r-t[x<<1|1].l+1;
t[x<<1|1].sum0=t[x<<1|1].r-t[x<<1|1].l+1;
}
//下传
//覆盖掉取反标记
t[x<<1].tag=0;
t[x<<1|1].tag=0;
//下传
t[x<<1].puttag=t[x].puttag;
t[x<<1|1].puttag=t[x].puttag;
//标记清空
t[x].puttag=-1;
}
if(t[x].tag){//处理区间取反
//取反
if(t[x].tag^t[x<<1].tag){
swap(t[x<<1].ans0,t[x<<1].ans1);
swap(t[x<<1].lmx0,t[x<<1].lmx1);
swap(t[x<<1].rmx0,t[x<<1].rmx1);
swap(t[x<<1].sum0,t[x<<1].sum1);
}
if(t[x].tag^t[x<<1|1].tag){
swap(t[x<<1|1].ans0,t[x<<1|1].ans1);
swap(t[x<<1|1].lmx0,t[x<<1|1].lmx1);
swap(t[x<<1|1].rmx0,t[x<<1|1].rmx1);
swap(t[x<<1|1].sum0,t[x<<1|1].sum1);
}
//下传
t[x<<1].tag^=t[x].tag;
t[x<<1|1].tag^=t[x].tag;
//标记清空
t[x].tag=0;
}
return;
}
void build(int x,int l,int r){
t[x].l=l;
t[x].r=r;
t[x].puttag=-1;
if(l==r){
if(a[l]){
t[x].ans1=1;
t[x].sum1=1;
t[x].rmx1=1;
t[x].lmx1=1;
}else{
t[x].ans0=1;
t[x].sum0=1;
t[x].rmx0=1;
t[x].lmx0=1;
}
return;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
return;
}
void change(int x,int l,int r,int d){
int L=t[x].l;
int R=t[x].r;
if(l<=L&&R<=r){
t[x].puttag=d;
t[x].tag=0;
if(d){
t[x].ans0=0;
t[x].lmx0=0;
t[x].rmx0=0;
t[x].sum0=0;
t[x].ans1=t[x].r-t[x].l+1;
t[x].lmx1=t[x].r-t[x].l+1;
t[x].rmx1=t[x].r-t[x].l+1;
t[x].sum1=t[x].r-t[x].l+1;
}else{
t[x].ans1=0;
t[x].lmx1=0;
t[x].rmx1=0;
t[x].sum1=0;
t[x].ans0=t[x].r-t[x].l+1;
t[x].lmx0=t[x].r-t[x].l+1;
t[x].rmx0=t[x].r-t[x].l+1;
t[x].sum0=t[x].r-t[x].l+1;
}
return;
}
push_down(x);
int mid=L+R>>1;
if(l<=mid)change(x<<1,l,r,d);
if(r>mid)change(x<<1|1,l,r,d);
t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
return;
}
void update(int x,int l,int r){
int L=t[x].l;
int R=t[x].r;
if(l<=L&&R<=r){
t[x].tag^=1;
swap(t[x].ans0,t[x].ans1);
swap(t[x].lmx0,t[x].lmx1);
swap(t[x].rmx0,t[x].rmx1);
swap(t[x].sum0,t[x].sum1);
return;
}
push_down(x);
int mid=L+R>>1;
if(l<=mid)update(x<<1,l,r);
if(r>mid) update(x<<1|1,l,r);
t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
return;
}
node query(int x,int l,int r){
int L=t[x].l;
int R=t[x].r;
if(l<=L&&R<=r)return t[x];
push_down(x);
node left=none;
node right=none;
bool lf=0,rt=0;
int mid=L+R>>1;
if(l<=mid)left=query(x<<1,l,r),lf=1;
if(r>mid) right=query(x<<1|1,l,r),rt=1;
if(lf&&rt)return push_up(none,left,right);
if(lf)return left;
return right;
}
void print_tree(int x){
int L=t[x].l;
int R=t[x].r;
cout<<x<<' '<<L<<' '<<R<<endl;
cout<<"ans "<<t[x].ans0<<' '<<t[x].ans1<<endl;
cout<<"sum "<<t[x].sum0<<' '<<t[x].sum1<<endl;
cout<<"lmx "<<t[x].lmx0<<' '<<t[x].lmx1<<endl;
cout<<"rmx "<<t[x].rmx0<<' '<<t[x].rmx1<<endl;
if(L==R)return;
cout<<"ls "<<x*2<<' '<<"rs"<<x*2+1<<endl;
print_tree(x<<1);
print_tree(x<<1|1);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",a+i);
build(1,1,n);
//print_tree(1);
while(m--){
scanf("%d%d%d",&x,&y,&z);
y++;
z++;
if(x==0)change(1,y,z,0);
if(x==1)change(1,y,z,1);
if(x==2)update(1,y,z);
if(x==3)printf("%d\n",query(1,y,z).sum1);
if(x==4)printf("%d\n",query(1,y,z).ans1);
//puts("NOWTREE");
//print_tree(1);
}
return 0;
}
by AK47N @ 2024-12-14 21:54:07
@Lian_lele
#include<bits/stdc++.h>
using namespace std;
int n,q,a[100001];
struct d{
int w,b,lw,lb,rw,rb,mw,mb;
d(int w=0,int b=0,int lw=0,int lb=0,int rw=0,int rb=0,int mw=0,int mb=0):
w(w),b(b),lw(lw),lb(lb),rw(rw),rb(rb),mw(mw),mb(mb){}
};
inline d hb(d i,d j){
return d(
i.w+j.w, i.b+j.b,
(i.b?i.lw:i.w+j.lw), (i.w?i.lb:i.b+j.lb),
(j.b?j.rw:j.w+i.rw), (j.w?j.rb:j.b+i.rb),
max(max(i.mw,j.mw),i.rw+j.lw),
max(max(i.mb,j.mb),i.rb+j.lb));
}
d dat[262144]; int len[262144],tg1[262144],tg2[262144];
inline void P(int i,int typ){
d&t=dat[i];
if(typ==0) tg2[i]= 0, tg1[i]=0, t=d(0,len[i],0,len[i],0,len[i],0,len[i]);
if(typ==1) tg2[i]= 0, tg1[i]=1, t=d(len[i],0,len[i],0,len[i],0,len[i],0);
if(typ==2) tg2[i]^=1, swap(t.w,t.b), swap(t.lw,t.lb), swap(t.rw,t.rb), swap(t.mw,t.mb);
}
inline void pd(int i){
if(~tg1[i]) P(i<<1,tg1[i]), P(i<<1|1,tg1[i]);
if(tg2[i]) P(i<<1,2), P(i<<1|1,2);
tg1[i]=-1, tg2[i]=0;
}
void build(int i,int l,int r){
len[i]=r-l+1; tg1[i]=-1;
if(l==r) {int t=a[l]; dat[i]=d(t,t^1,t,t^1,t,t^1,t,t^1); return;}
build(i<<1,l,l+r>>1);
build(i<<1|1,(l+r>>1)+1,r);
dat[i]=hb(dat[i<<1],dat[i<<1|1]);
}
void Mdf(int i,int l,int r,int a,int b,int t){
if(b<l||r<a) return; if(a<=l&&r<=b) {P(i,t); return;}
pd(i); Mdf(i<<1,l,l+r>>1,a,b,t), Mdf(i<<1|1,(l+r>>1)+1,r,a,b,t);
dat[i]=hb(dat[i<<1],dat[i<<1|1]);
}
d Qur(int i,int l,int r,int a,int b){
if(b<l||r<a) return d(); if(a<=l&&r<=b) return dat[i];
pd(i); return hb(Qur(i<<1,l,l+r>>1,a,b),Qur(i<<1|1,(l+r>>1)+1,r,a,b));
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i) scanf("%d",a+i);
build(1,1,n);
for(int i=1;i<=q;++i){
int opt,l,r;
scanf("%d%d%d",&opt,&l,&r); ++l, ++r;
if(opt<3) Mdf(1,1,n,l,r,opt);
else {d t=Qur(1,1,n,l,r); printf("%d\n",opt==3?t.w:t.mw);}
}
return 0;
}
by Lian_zy @ 2024-12-14 21:57:44
@AK47N 谢谢,但是能不能帮忙调下代码啊
这是第一篇题解吧
by Liuhy2996 @ 2024-12-14 22:51:59
@Lian_lele 把81行和87行的if去掉试试
by Liuhy2996 @ 2024-12-14 22:55:55
@Lian_lele
#include<bits/stdc++.h>
#define N 100005
using namespace std;
//区间变0/1 ->tag
//区间取反 ->puttag
//区间和 ->sum0/sum1
//区间最长连续1 ->ans0,ans1,rmx0,rmx1,lmx0,lmx1
struct node{
int l,r;
int sum0,sum1;
int ans0,ans1,rmx0,rmx1,lmx0,lmx1;
int tag,puttag;
}none,t[N<<2];
int n,m,x,y,z,a[N];
node push_up(node ans,node ls,node rs){
ans.sum0=ls.sum0+rs.sum0;
ans.sum1=ls.sum1+rs.sum1;
//从左/右起最长的连续0/1
//left
ans.lmx0=ls.lmx0+(ls.lmx0==ls.r-ls.l+1)*rs.lmx0;
ans.lmx1=ls.lmx1+(ls.lmx1==ls.r-ls.l+1)*rs.lmx1;
//right
ans.rmx0=rs.rmx0+(rs.rmx0==rs.r-rs.l+1)*ls.rmx0;
ans.rmx1=rs.rmx1+(rs.rmx1==rs.r-rs.l+1)*ls.rmx1;
//获取ans
ans.ans0=max(max(ls.ans0,rs.ans0),ls.rmx0+rs.lmx0);
ans.ans1=max(max(ls.ans1,rs.ans1),ls.rmx1+rs.lmx1);
return ans;
}
void push_down(int x){
//先赋值再取反
if(~t[x].puttag){//处理区间赋值标记
if(t[x].puttag){//标记:区间赋1
t[x<<1].ans0=0;
t[x<<1].lmx0=0;
t[x<<1].rmx0=0;
t[x<<1].sum0=0;
t[x<<1].ans1=t[x<<1].r-t[x<<1].l+1;
t[x<<1].lmx1=t[x<<1].r-t[x<<1].l+1;
t[x<<1].rmx1=t[x<<1].r-t[x<<1].l+1;
t[x<<1].sum1=t[x<<1].r-t[x<<1].l+1;
t[x<<1|1].ans0=0;
t[x<<1|1].lmx0=0;
t[x<<1|1].rmx0=0;
t[x<<1|1].sum0=0;
t[x<<1|1].ans1=t[x<<1|1].r-t[x<<1|1].l+1;
t[x<<1|1].lmx1=t[x<<1|1].r-t[x<<1|1].l+1;
t[x<<1|1].rmx1=t[x<<1|1].r-t[x<<1|1].l+1;
t[x<<1|1].sum1=t[x<<1|1].r-t[x<<1|1].l+1;
}else{//区间赋0
t[x<<1].ans1=0;
t[x<<1].lmx1=0;
t[x<<1].rmx1=0;
t[x<<1].sum1=0;
t[x<<1].ans0=t[x<<1].r-t[x<<1].l+1;
t[x<<1].lmx0=t[x<<1].r-t[x<<1].l+1;
t[x<<1].rmx0=t[x<<1].r-t[x<<1].l+1;
t[x<<1].sum0=t[x<<1].r-t[x<<1].l+1;
t[x<<1|1].ans1=0;
t[x<<1|1].lmx1=0;
t[x<<1|1].rmx1=0;
t[x<<1|1].sum1=0;
t[x<<1|1].ans0=t[x<<1|1].r-t[x<<1|1].l+1;
t[x<<1|1].lmx0=t[x<<1|1].r-t[x<<1|1].l+1;
t[x<<1|1].rmx0=t[x<<1|1].r-t[x<<1|1].l+1;
t[x<<1|1].sum0=t[x<<1|1].r-t[x<<1|1].l+1;
}
//下传
//覆盖掉取反标记
t[x<<1].tag=0;
t[x<<1|1].tag=0;
//下传
t[x<<1].puttag=t[x].puttag;
t[x<<1|1].puttag=t[x].puttag;
//标记清空
t[x].puttag=-1;
}
if(t[x].tag){//处理区间取反
//取反
//if(t[x].tag^t[x<<1].tag){
swap(t[x<<1].ans0,t[x<<1].ans1);
swap(t[x<<1].lmx0,t[x<<1].lmx1);
swap(t[x<<1].rmx0,t[x<<1].rmx1);
swap(t[x<<1].sum0,t[x<<1].sum1);
//}
//if(t[x].tag^t[x<<1|1].tag){
swap(t[x<<1|1].ans0,t[x<<1|1].ans1);
swap(t[x<<1|1].lmx0,t[x<<1|1].lmx1);
swap(t[x<<1|1].rmx0,t[x<<1|1].rmx1);
swap(t[x<<1|1].sum0,t[x<<1|1].sum1);
//}
//下传
t[x<<1].tag^=t[x].tag;
t[x<<1|1].tag^=t[x].tag;
//标记清空
t[x].tag=0;
}
return;
}
void build(int x,int l,int r){
t[x].l=l;
t[x].r=r;
t[x].puttag=-1;
if(l==r){
if(a[l]){
t[x].ans1=1;
t[x].sum1=1;
t[x].rmx1=1;
t[x].lmx1=1;
}else{
t[x].ans0=1;
t[x].sum0=1;
t[x].rmx0=1;
t[x].lmx0=1;
}
return;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
return;
}
void change(int x,int l,int r,int d){
int L=t[x].l;
int R=t[x].r;
if(l<=L&&R<=r){
t[x].puttag=d;
t[x].tag=0;
if(d){
t[x].ans0=0;
t[x].lmx0=0;
t[x].rmx0=0;
t[x].sum0=0;
t[x].ans1=t[x].r-t[x].l+1;
t[x].lmx1=t[x].r-t[x].l+1;
t[x].rmx1=t[x].r-t[x].l+1;
t[x].sum1=t[x].r-t[x].l+1;
}else{
t[x].ans1=0;
t[x].lmx1=0;
t[x].rmx1=0;
t[x].sum1=0;
t[x].ans0=t[x].r-t[x].l+1;
t[x].lmx0=t[x].r-t[x].l+1;
t[x].rmx0=t[x].r-t[x].l+1;
t[x].sum0=t[x].r-t[x].l+1;
}
return;
}
push_down(x);
int mid=L+R>>1;
if(l<=mid)change(x<<1,l,r,d);
if(r>mid)change(x<<1|1,l,r,d);
t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
return;
}
void update(int x,int l,int r){
int L=t[x].l;
int R=t[x].r;
if(l<=L&&R<=r){
t[x].tag^=1;
swap(t[x].ans0,t[x].ans1);
swap(t[x].lmx0,t[x].lmx1);
swap(t[x].rmx0,t[x].rmx1);
swap(t[x].sum0,t[x].sum1);
return;
}
push_down(x);
int mid=L+R>>1;
if(l<=mid)update(x<<1,l,r);
if(r>mid) update(x<<1|1,l,r);
t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
return;
}
node query(int x,int l,int r){
int L=t[x].l;
int R=t[x].r;
if(l<=L&&R<=r)return t[x];
push_down(x);
node left=none;
node right=none;
bool lf=0,rt=0;
int mid=L+R>>1;
if(l<=mid)left=query(x<<1,l,r),lf=1;
if(r>mid) right=query(x<<1|1,l,r),rt=1;
if(lf&&rt)return push_up(none,left,right);
if(lf)return left;
return right;
}
void print_tree(int x){
int L=t[x].l;
int R=t[x].r;
cout<<x<<' '<<L<<' '<<R<<endl;
cout<<"ans "<<t[x].ans0<<' '<<t[x].ans1<<endl;
cout<<"sum "<<t[x].sum0<<' '<<t[x].sum1<<endl;
cout<<"lmx "<<t[x].lmx0<<' '<<t[x].lmx1<<endl;
cout<<"rmx "<<t[x].rmx0<<' '<<t[x].rmx1<<endl;
if(L==R)return;
cout<<"ls "<<x*2<<' '<<"rs"<<x*2+1<<endl;
print_tree(x<<1);
print_tree(x<<1|1);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",a+i);
build(1,1,n);
//print_tree(1);
while(m--){
scanf("%d%d%d",&x,&y,&z);
y++;
z++;
if(x==0)change(1,y,z,0);
if(x==1)change(1,y,z,1);
if(x==2)update(1,y,z);
if(x==3)printf("%d\n",query(1,y,z).sum1);
if(x==4)printf("%d\n",query(1,y,z).ans1);
//puts("NOWTREE");
//print_tree(1);
}
return 0;
}
by Lian_zy @ 2024-12-14 23:06:55
@Liuhy2996 A了,谢谢你,关注啦