无语了,hick过了其它没过,求助(悬赏关注)
#include<bits/stdc++.h>
using namespace std;
const int N=200020;
int n,m,a[N];
int max(int a,int b){return a>b?a:b;}
struct Tree{
int add,rev,l,r;
int num1,amax1,lmax1,rmax1;
int num0,amax0,lmax0,rmax0;
}e[N<<2];
#define lid id<<1
#define rid id<<1|1
#define l(u) e[u].l
#define r(u) e[u].r
#define rev(u) e[u].rev
#define add(u) e[u].add
#define num1(u) e[u].num1
#define num0(u) e[u].num0
#define lmax1(u) e[u].lmax1
#define lmax0(u) e[u].lmax0
#define rmax1(u) e[u].rmax1
#define rmax0(u) e[u].rmax0
#define amax1(u) e[u].amax1
#define amax0(u) e[u].amax0
inline void push_up(int id){
{
num1(id)=num1(lid)+num1(rid);
lmax1(id)=lmax1(lid);
if(num1(lid)==r(lid)-l(lid)+1) lmax1(id)+=lmax1(rid);
rmax1(id)=rmax1(rid);
if(num1(rid)==r(rid)-l(rid)+1) rmax1(id)+=rmax1(lid);
amax1(id)=lmax1(rid)+rmax1(lid);
amax1(id)=max(amax1(id),amax1(lid));
amax1(id)=max(amax1(id),amax1(rid));
}
{
num0(id)=num0(lid)+num0(rid);
lmax0(id)=lmax0(lid);
if(num0(lid)==r(lid)-l(lid)+1) lmax0(id)+=lmax0(rid);
rmax0(id)=rmax0(rid);
if(num0(rid)==r(rid)-l(rid)+1) rmax0(id)+=rmax0(lid);
amax0(id)=lmax0(rid)+rmax0(lid);
amax0(id)=max(amax0(id),amax0(lid));
amax0(id)=max(amax0(id),amax0(rid));
}
return;
}
inline void build(int id,int l,int r){
l(id)=l,r(id)=r,add(id)=-1;
if(l==r){
num0(id)=lmax0(id)=rmax0(id)=amax0(id)=a[l]==0;
num1(id)=lmax1(id)=rmax1(id)=amax1(id)=a[l]==1;
return;
}
int mid=l+r>>1;
build(lid,l,mid),build(rid,mid+1,r);
push_up(id);
}
inline void push_down(int id){
if(add(id)!=-1){
rev(id)=0;
if(add(id)==0){
{
add(lid)=0,rev(lid)=0;
num1(lid)=amax1(lid)=lmax1(lid)=rmax1(lid)=0;
num0(lid)=amax0(lid)=lmax0(lid)=rmax0(lid)=(r(lid)-l(lid)+1);
}
{
add(rid)=0,rev(rid)=0;
num1(rid)=amax1(rid)=lmax1(rid)=rmax1(rid)=0;
num0(rid)=amax0(rid)=lmax0(rid)=rmax0(rid)=(r(rid)-l(rid)+1);
}
add(id)=-1;
return;
}
if(add(id)==1){
{
add(lid)=1,rev(lid)=0;
num0(lid)=amax0(lid)=lmax0(lid)=rmax0(lid)=0;
num1(lid)=amax1(lid)=lmax1(lid)=rmax1(lid)=(r(lid)-l(lid)+1);
}
{
add(rid)=1,rev(rid)=0;
num0(rid)=amax0(rid)=lmax0(rid)=rmax0(rid)=0;
num1(rid)=amax1(rid)=lmax1(rid)=rmax1(rid)=(r(rid)-l(rid)+1);
}
add(id)=-1;
return;
}
}
if(rev(id)){
swap(num1(lid),num0(lid));
swap(num1(rid),num0(rid));
if(add(lid)!=-1) add(lid)^=1;
else rev(lid)^=1;
if(add(rid)!=-1) add(rid)^=1;
else rev(add(rid))^=1;
swap(amax1(lid),amax0(lid));
swap(lmax1(lid),lmax0(lid));
swap(rmax1(lid),rmax0(lid));
swap(amax1(rid),amax0(rid));
swap(lmax1(rid),lmax0(rid));
swap(rmax1(rid),rmax0(rid));
rev(id)=0;
return;
}
return;
}
inline void modify(int id,int x,int y,int q){
push_down(id);
if(x==l(id)&&r(id)==y){
if(q==0){
add(id)=0;
num1(id)=amax1(id)=lmax1(id)=rmax1(id)=0;
num0(id)=amax0(id)=lmax0(id)=rmax0(id)=(r(id)-l(id)+1);
return;
}
if(q==1){
add(id)=1;
num0(id)=amax0(id)=lmax0(id)=rmax0(id)=0;
num1(id)=amax1(id)=lmax1(id)=rmax1(id)=(r(id)-l(id)+1);
return;
}
if(q==2){
rev(id)^=1;
swap(num1(id),num0(id));
swap(amax1(id),amax0(id));
swap(lmax1(id),lmax0(id));
swap(rmax1(id),rmax0(id));
return;
}
}
int mid=l(id)+r(id)>>1;
if(mid<x) modify(rid,x,y,q);
else if(mid>=y) modify(lid,x,y,q);
else modify(lid,x,mid,q),modify(rid,mid+1,y,q);
push_up(id);
return;
}
inline int query1(int id,int x,int y){
push_down(id);
if(x==l(id)&&r(id)==y) return num1(id);
int mid=l(id)+r(id)>>1;
if(mid<x) return query1(rid,x,y);
else if(mid>=y) return query1(lid,x,y);
return query1(lid,x,mid)+query1(rid,mid+1,y);
}
inline Tree query2(int id,int x,int y){
push_down(id);
if(x==l(id)&&r(id)==y) return e[id];
int mid=l(id)+r(id)>>1;
if(mid<x) return query2(rid,x,y);
else if(mid>=y) return query2(lid,x,y);
else{
Tree ret,L=query2(lid,x,mid),R=query2(rid,mid+1,y);
ret.num1=L.num1+R.num1;
ret.num0=L.num0+R.num0;
ret.lmax1=L.lmax1;
if(L.num1==L.r-L.l+1){
ret.lmax1+=R.lmax1;
}
ret.lmax0=L.lmax0;
if(L.num0==L.r-L.l+1){
ret.lmax0+=R.lmax0;
}
ret.rmax1=R.rmax1;
if(R.num1==R.r-R.l+1){
ret.rmax1+=L.rmax1;
}
ret.rmax0=R.rmax0;
if(R.num0==R.r-R.l+1){
ret.rmax0+=L.rmax0;
}
ret.amax1=R.lmax1+L.rmax1;
ret.amax1=max(ret.amax1,L.amax1);
ret.amax1=max(ret.amax1,R.amax1);
ret.amax0=R.lmax0+L.rmax0;
ret.amax0=max(ret.amax0,L.amax0);
ret.amax0=max(ret.amax0,R.amax0);
return ret;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
while(m--){
int x,y,op;
scanf("%d%d%d",&op,&x,&y);
x++;y++;
if(op==0||op==1||op==2){
modify(1,x,y,op);
}else if(op==3){
printf("%d\n",query1(1,x,y));
}else if(op==4){
printf("%d\n",query2(1,x,y).amax1);
}
}
return 0;
}