Langke_Saonian @ 2024-07-23 12:32:34
#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];
// definitions and comments
#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
//rev 标记是否翻转
//num1(the number of 1)
//num0(the number of 0)
//amax1(all max of 1)
//amax0(all max of 0)
//lmax1(left max of 1)
//lmax0(left max of 0)
//rmax1(right max of 1)
//rmax0(right max of 0)
/*
add
-1: do nothing
0: all of number become 0
1: all of number become 1
*/
inline void push_up(int id){
//cout<<"a";
{//the change of 1
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));
}
{//the change of 0
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){
//cout<<"b";
if(add(id)!=-1){
rev(id)=0;
if(add(id)==0){
{//the change of lid
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);
}
{//the change of rid
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){
{//the change of lid
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);
}
{//the change of rid
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);
// int dep=log2(n);
// dep=pow(2,dep+1);
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;
}
by Langke_Saonian @ 2024-07-23 15:21:46
破案了
by Langke_Saonian @ 2024-07-23 15:25:55
我在113行 push_down 时写错了
应是rev(rid)^=1;
by Langke_Saonian @ 2024-07-23 15:26:27
结帖