写了三个中午加一个晚上,还是0pt,哪位巨佬能帮我看一下?
#include<bits/stdc++.h>
using namespace std;
const int N=114514;
int n,m;
int a[N];
struct segment_tree{
int l;
int r;
int l0; //左起0
int l1; //左起1
int r0; //右起0
int r1; //右起1
int tot0; //总共0
int tot1; //总共1
int sum0; //连续0
int sum1; //连续1
int tag;
}tree[4*N];
void pushup(int id){
tree[id].l0=tree[id*2].l0;
if(tree[id*2].tot1==0){
tree[id].l0=tree[id*2].tot0+tree[id*2+1].l0;
}
tree[id].r0=tree[id*2+1].r0;
if(tree[id*2+1].tot1==0){
tree[id].r0=tree[id*2+1].tot0+tree[id*2].r0;
}
tree[id].l1=tree[id*2].l1;
if(tree[id*2].tot0==0){
tree[id].l1=tree[id*2].tot1+tree[id*2+1].l1;
}
tree[id].r1=tree[id*2+1].r1;
if(tree[id*2+1].tot0==0){
tree[id].r1=tree[id*2+1].tot1+tree[id*2].r1;
}
tree[id].tot0=tree[id*2].tot0+tree[id*2+1].tot0;
tree[id].tot1=tree[id*2].tot1+tree[id*2+1].tot1;
tree[id].sum0=max(tree[id*2].r0+tree[id*2+1].l0,max(tree[id*2].sum0,tree[id*2+1].sum0));
tree[id].sum1=max(tree[id*2].r1+tree[id*2+1].l1,max(tree[id*2].sum1,tree[id*2+1].sum1));
}
void pushdown(int id){
if(tree[id].tag==-1) return;
if(tree[id].tag==0){
tree[id*2].tag=0;
tree[id*2].tot0+=tree[id*2].tot1;
tree[id*2].l1=tree[id*2].r1=tree[id*2].sum1=tree[id*2].tot1=0;
tree[id*2].l0=tree[id*2].r0=tree[id*2].sum0=tree[id*2].tot0;
tree[id*2+1].tag=0;
tree[id*2+1].tot0+=tree[id*2+1].tot1;
tree[id*2+1].l1=tree[id*2+1].r1=tree[id*2+1].sum1=tree[id*2+1].tot1=0;
tree[id*2+1].l0=tree[id*2+1].r0=tree[id*2+1].sum0=tree[id*2+1].tot0;
tree[id].tag=-1;
return;
}
if(tree[id].tag==1){
tree[id*2].tag=1;
tree[id*2].tot1+=tree[id*2].tot0;
tree[id*2].l0=tree[id*2].r0=tree[id*2].sum0=tree[id*2].tot0=0;
tree[id*2].l1=tree[id*2].r1=tree[id*2].sum1=tree[id*2].tot1;
tree[id*2+1].tag=1;
tree[id*2+1].tot1+=tree[id*2+1].tot0;
tree[id*2+1].l0=tree[id*2+1].r0=tree[id*2+1].sum0=tree[id*2+1].tot0=0;
tree[id*2+1].l1=tree[id*2+1].r1=tree[id*2+1].sum1=tree[id*2+1].tot1;
tree[id].tag=-1;
return;
}
if(tree[id*2].tag==2){
tree[id*2].tag=-1;
}
else if(tree[id*2].tag==1){
tree[id*2].tag=0;
tree[id*2].tot0+=tree[id*2].tot1;
tree[id*2].l1=tree[id*2].r1=tree[id*2].sum1=tree[id*2].tot1=0;
tree[id*2].l0=tree[id*2].r0=tree[id*2].sum0=tree[id*2].tot0;
}
else if(tree[id*2].tag==0){
tree[id*2].tag=1;
tree[id*2].tot1+=tree[id*2].tot0;
tree[id*2].l0=tree[id*2].r0=tree[id*2].sum0=tree[id*2].tot0=0;
tree[id*2].l1=tree[id*2].r1=tree[id*2].sum1=tree[id*2].tot1;
}
else{
tree[id*2].tag=2;
swap(tree[id*2].l0,tree[id*2].l1);
swap(tree[id*2].r0,tree[id*2].r1);
swap(tree[id*2].tot0,tree[id*2].tot1);
swap(tree[id*2].sum0,tree[id*2].sum1);
}
if(tree[id*2+1].tag==2){
tree[id*2+1].tag=-1;
}
else if(tree[id*2+1].tag==1){
tree[id*2+1].tag=0;
tree[id*2+1].tot0+=tree[id*2+1].tot1;
tree[id*2+1].l1=tree[id*2+1].r1=tree[id*2+1].sum1=tree[id*2+1].tot1=0;
tree[id*2+1].l0=tree[id*2+1].r0=tree[id*2+1].sum0=tree[id*2+1].tot0;
}
else if(tree[id*2+1].tag==0){
tree[id*2+1].tag=1;
tree[id*2+1].tot1+=tree[id*2+1].tot0;
tree[id*2+1].l0=tree[id*2+1].r0=tree[id*2+1].sum0=tree[id*2+1].tot0=0;
tree[id*2+1].l1=tree[id*2+1].r1=tree[id*2+1].sum1=tree[id*2+1].tot1;
}
else{
tree[id*2+1].tag=2;
swap(tree[id*2+1].l0,tree[id*2+1].l1);
swap(tree[id*2+1].r0,tree[id*2+1].r1);
swap(tree[id*2+1].tot0,tree[id*2+1].tot1);
swap(tree[id*2+1].sum0,tree[id*2+1].sum1);
}
tree[id].tag=-1;
return;
}
void build(int id,int l,int r){
tree[id].l=l;
tree[id].r=r;
tree[id].tag=-1;
if(l==r){
if(a[l]==0){
tree[id].l0=1;
tree[id].r0=1;
tree[id].sum0=1;
tree[id].tot0=1;
}
else{
tree[id].l1=1;
tree[id].r1=1;
tree[id].sum1=1;
tree[id].tot1=1;
}
return;
}
int mid=l+r>>1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
pushup(id);
}
void query0(int id,int l,int r){
int l2=tree[id].l;
int r2=tree[id].r;
if(l2>=l&&r2<=r){
tree[id].tag=0;
tree[id].tot0+=tree[id].tot1;
tree[id].l1=tree[id].r1=tree[id].sum1=tree[id].tot1=0;
tree[id].l0=tree[id].r0=tree[id].sum0=tree[id].tot0;
return;
}
pushdown(id);
int mid=l2+r2>>1;
if(l<=mid) query0(id*2,l,r);
if(r>mid) query0(id*2+1,l,r);
pushup(id);
}
void query1(int id,int l,int r){
int l2=tree[id].l;
int r2=tree[id].r;
if(l2>=l&&r2<=r){
tree[id].tag=1;
tree[id].tot1+=tree[id].tot0;
tree[id].l0=tree[id].r0=tree[id].sum0=tree[id].tot0=0;
tree[id].l1=tree[id].r1=tree[id].sum1=tree[id].tot1;
return;
}
pushdown(id);
int mid=l2+r2>>1;
if(l<=mid) query1(id*2,l,r);
if(r>mid) query1(id*2+1,l,r);
pushup(id);
}
void query2(int id,int l,int r){
int l2=tree[id].l;
int r2=tree[id].r;
if(l2>=l&&r2<=r){
// cout<<l2<<' '<<r2<<endl;
if(tree[id].tag==2) tree[id].tag=-1;
else if(tree[id].tag==1){
tree[id].tag=0;
tree[id].tot0+=tree[id].tot1;
tree[id].l1=tree[id].r1=tree[id].sum1=tree[id].tot1=0;
tree[id].l0=tree[id].r0=tree[id].sum0=tree[id].tot0;
}
else if(tree[id].tag==0){
tree[id].tag=1;
tree[id].tot1+=tree[id].tot0;
tree[id].l0=tree[id].r0=tree[id].sum0=tree[id].tot0=0;
tree[id].l1=tree[id].r1=tree[id].sum1=tree[id].tot1;
}
else{
tree[id].tag=2;
swap(tree[id].l0,tree[id].l1);
swap(tree[id].r0,tree[id].r1);
swap(tree[id].tot0,tree[id].tot1);
swap(tree[id].sum0,tree[id].sum1);
}
return;
}
pushdown(id);
int mid=l2+r2>>1;
if(l<=mid) query2(id*2,l,r);
if(r>mid) query2(id*2+1,l,r);
pushup(id);
}
int query3(int id,int l,int r){
int l2=tree[id].l;
int r2=tree[id].r;
if(l2>=l&&r2<=r){
return tree[id].tot1;
}
pushdown(id);
int mid=l2+r2>>1;
int ans=0;
if(l<=mid) ans+=query3(id*2,l,r);
if(r>mid) ans+=query3(id*2+1,l,r);
pushup(id);
return ans;
}
segment_tree query4(int id,int l,int r){
int l2=tree[id].l;
int r2=tree[id].r;
if(l2>=l&&r2<=r){
return tree[id];
}
pushdown(id);
int mid=l2+r2>>1;
segment_tree ret,ret1,ret2;
if(r<=mid) return query4(id*2,l,r);
if(l>mid) return query4(id*2+1,l,r);
ret1=query4(id*2,l,r);
ret2=query4(id*2+1,l,r);
ret.l0=ret1.l0;
if(ret1.tot1==0){
ret.l0=ret1.tot0+ret2.l0;
}
ret.r0=ret2.r0;
if(ret2.tot1==0){
ret.r0=ret2.tot0+ret1.r0;
}
ret.l1=ret1.l1;
if(ret1.tot0==0){
ret.l1=ret1.tot1+ret2.l1;
}
ret.r1=ret2.r1;
if(ret2.tot0==0){
ret.r1=ret2.tot1+ret1.r1;
}
ret.tot0=ret1.tot0+ret2.tot0;
ret.tot1=ret1.tot1+ret2.tot1;
ret.sum0=max(ret1.r0+ret2.l0,max(ret1.sum0,ret2.sum0));
ret.sum1=max(ret1.r1+ret2.l1,max(ret1.sum1,ret2.sum1));
return ret;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
build(1,0,n-1);
while(m--){
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
switch(op){
case 0:query0(1,l,r);break;
case 1:query1(1,l,r);break;
case 2:query2(1,l,r);break;
case 3:printf("%d\n",query3(1,l,r));break;
case 4:printf("%d\n",query4(1,l,r).sum1);break;
}
}
return 0;
}
多谢了。