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;
}