xtzqhywww @ 2024-02-23 16:01:52
为什么pushdown改个位置就能过
ac代码
#include<bits/stdc++.h>
#define re register
#define int long long
using namespace std;
const int N=1e5+10;
int n,Q;
int a[N];
struct node{
int sum,l1,r1,l0,r0,len,len1,len0,add,add1,l,r;
}tr[N<<2];
inline void up(int p){
tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
tr[p].len1=max(tr[p<<1].len1,tr[p<<1|1].len1);
tr[p].len0=max(tr[p<<1].len0,tr[p<<1|1].len0);
if(tr[p<<1].r1>0&&tr[p<<1|1].l1>0) tr[p].len1=max(tr[p].len1,tr[p<<1].r1+tr[p<<1|1].l1);
if(tr[p<<1].r0>0&&tr[p<<1|1].l0>0) tr[p].len0=max(tr[p].len0,tr[p<<1].r0+tr[p<<1|1].l0);
if(tr[p<<1].l1==tr[p<<1].len&&tr[p<<1|1].l1>0) tr[p].l1=tr[p<<1].l1+tr[p<<1|1].l1;
else tr[p].l1=tr[p<<1].l1;
if(tr[p<<1].l0==tr[p<<1].len&&tr[p<<1|1].l0>0) tr[p].l0=tr[p<<1].l0+tr[p<<1|1].l0;
else tr[p].l0=tr[p<<1].l0;
if(tr[p<<1|1].r1==tr[p<<1|1].len&&tr[p<<1].r1>0) tr[p].r1=tr[p<<1|1].r1+tr[p<<1].r1;
else tr[p].r1=tr[p<<1|1].r1;
if(tr[p<<1|1].r0==tr[p<<1|1].len&&tr[p<<1].r0>0) tr[p].r0=tr[p<<1|1].r0+tr[p<<1].r0;
else tr[p].r0=tr[p<<1|1].r0;
}
inline void down(int p){
int s=tr[p].l,t=tr[p].r,m=s+((t-s)>>1);
if(tr[p].add1==0){
tr[p<<1].sum=tr[p<<1].l1=tr[p<<1].r1=tr[p<<1].len1=0;
tr[p<<1].l0=tr[p<<1].r0=tr[p<<1].len0=(m-s+1);
tr[p<<1|1].sum=tr[p<<1|1].l1=tr[p<<1|1].r1=tr[p<<1|1].len1=0;
tr[p<<1|1].l0=tr[p<<1|1].r0=tr[p<<1|1].len0=(t-m);
tr[p<<1].add1=0;
tr[p<<1|1].add1=0;
tr[p].add1=-1;
tr[p<<1].add=tr[p<<1|1].add=tr[p].add=0;
}
else if(tr[p].add1==1){
tr[p<<1].sum=tr[p<<1].l1=tr[p<<1].r1=tr[p<<1].len1=(m-s+1);
tr[p<<1].l0=tr[p<<1].r0=tr[p<<1].len0=0;
tr[p<<1|1].sum=tr[p<<1|1].l1=tr[p<<1|1].r1=tr[p<<1|1].len1=(t-m);
tr[p<<1|1].l0=tr[p<<1|1].r0=tr[p<<1|1].len0=0;
tr[p<<1].add1=1;
tr[p<<1|1].add1=1;
tr[p].add1=-1;
tr[p<<1].add=tr[p<<1|1].add=tr[p].add=0;
}
if(tr[p].add){
tr[p<<1].sum=(m-s+1)-tr[p<<1].sum;
tr[p<<1|1].sum=(t-m)-tr[p<<1|1].sum;
if(tr[p<<1].add1!=-1) tr[p<<1].add1^=1;
else tr[p<<1].add^=1;
if(tr[p<<1|1].add1!=-1) tr[p<<1|1].add1^=1;
else tr[p<<1|1].add^=1;
swap(tr[p<<1].l1,tr[p<<1].l0);
swap(tr[p<<1].r1,tr[p<<1].r0);
swap(tr[p<<1].len1,tr[p<<1].len0);
swap(tr[p<<1|1].l1,tr[p<<1|1].l0);
swap(tr[p<<1|1].r1,tr[p<<1|1].r0);
swap(tr[p<<1|1].len1,tr[p<<1|1].len0);
tr[p].add=0;
}
}
inline void build(int l,int r,int p){
tr[p].add1=-1;
tr[p].len=(r-l+1);
tr[p].l=l,tr[p].r=r;
if(l==r){
if(a[l]) tr[p].sum=tr[p].len1=tr[p].l1=tr[p].r1=tr[p].len,tr[p].l0=tr[p].r0=tr[p].len0=0;
else tr[p].sum=tr[p].len1=tr[p].l1=tr[p].r1=0,tr[p].l0=tr[p].r0=tr[p].len0=tr[p].len;
return;
}
int m=l+((r-l)>>1);
build(l,m,p<<1);
build(m+1,r,p<<1|1);
up(p);
}
inline void change_0(int l,int r,int s,int t,int p){
down(p);
if(l<=s&&r>=t){
tr[p].sum=tr[p].l1=tr[p].r1=tr[p].len1=0;
tr[p].l0=tr[p].r0=tr[p].len0=tr[p].len;
tr[p].add1=0;
return;
}
int m=s+((t-s)>>1);
if(l<=m) change_0(l,r,s,m,p<<1);
if(r>m) change_0(l,r,m+1,t,p<<1|1);
up(p);
}
inline void change_1(int l,int r,int s,int t,int p){
down(p);
if(l<=s&&r>=t){
tr[p].sum=tr[p].l1=tr[p].r1=tr[p].len1=tr[p].len;
tr[p].l0=tr[p].r0=tr[p].len0=0;
tr[p].add1=1;
return;
}
int m=s+((t-s)>>1);
if(l<=m) change_1(l,r,s,m,p<<1);
if(r>m) change_1(l,r,m+1,t,p<<1|1);
up(p);
}
inline void change_swap(int l,int r,int s,int t,int p){
down(p);
if(l<=s&&r>=t){
tr[p].sum=tr[p].len-tr[p].sum;
swap(tr[p].l1,tr[p].l0);
swap(tr[p].r1,tr[p].r0);
swap(tr[p].len1,tr[p].len0);
tr[p].add^=1;
return;
}
int m=s+((t-s)>>1);
if(l<=m) change_swap(l,r,s,m,p<<1);
if(r>m) change_swap(l,r,m+1,t,p<<1|1);
up(p);
}
inline int query_sum(int l,int r,int s,int t,int p){
down(p);
if(l<=s&&r>=t) return tr[p].sum;
int m=s+((t-s)>>1),res=0;
if(l<=m) res+=query_sum(l,r,s,m,p<<1);
if(r>m) res+=query_sum(l,r,m+1,t,p<<1|1);
return res;
}
inline node query_len(int l,int r,int p){
down(p);
if(tr[p].l==l&&tr[p].r==r) return tr[p];
int m=tr[p].l+((tr[p].r-tr[p].l)>>1);
if(m<l) return query_len(l,r,p<<1|1);
else if(m>=r) return query_len(l,r,p<<1);
else{
node L=query_len(l,m,p<<1),R=query_len(m+1,r,p<<1|1),res;
res.sum=L.sum+R.sum;
if(L.sum==L.len) res.l1=L.len+R.l1;
else res.l1=L.l1;
if(L.sum==0) res.l0=L.len+R.l0;
else res.l0=L.l0;
if(R.sum==R.len) res.r1=L.r1+R.len;
else res.r1=R.r1;
if(R.sum==0) res.r0=L.r0+R.len;
else res.r0=R.r0;
res.len1=L.r1+R.l1;
res.len0=L.r0+R.l0;
res.len1=max(max(L.len1,R.len1),res.len1);
res.len0=max(max(L.len0,R.len0),res.len0);
return res;
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>Q;
for(re int i=1;i<=n;++i) cin>>a[i];
build(1,n,1);
while(Q--){
int op,x,y;
cin>>op>>x>>y;
x++,y++;
if(op==0) change_0(x,y,1,n,1);//cout<<"change_0"<<'\n';
if(op==1) change_1(x,y,1,n,1);//cout<<"change_1"<<'\n';
if(op==2) change_swap(x,y,1,n,1);//cout<<"change_swap"<<'\n';
if(op==3){
//int po=query_sum(x,y,1,n,1);
//cout<<"sum"<<'\n';
cout<<query_sum(x,y,1,n,1)<<'\n';
}
if(op==4){
//int po=query_len(x,y,1,n,1);
//cout<<"len"<<'\n';
cout<<query_len(x,y,1).len1<<'\n';
}
// cout<<x<<" "<<y<<" "<<'\n';
// if(op==3) cout<<"ans="<<query_sum(x,y,1,n,1);
// if(op==4) cout<<"ans="<<query_len(x,y,1,n,1).len1;
// cout<<'\n';
// for(re int i=1;i<=n;++i) cout<<query_sum(i,i,1,n,1)<<" ";
// cout<<'\n';
}
//for(re int i=1;i<=n*n;++i) cout<<tr[i].len<<" "<<tr[i].len1<<" "<<tr[i].l1<<" "<<tr[i].r1<<'\n';
return 0;
}20pts代码
#include<bits/stdc++.h>
#define re register
#define int long long
using namespace std;
const int N=1e5+10;
int n,Q;
int a[N];
struct node{
int sum,l1,r1,l0,r0,len,len1,len0,add,add1,l,r;
}tr[N<<2];
inline void up(int p){
tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
tr[p].len1=max(tr[p<<1].len1,tr[p<<1|1].len1);
tr[p].len0=max(tr[p<<1].len0,tr[p<<1|1].len0);
if(tr[p<<1].r1>0&&tr[p<<1|1].l1>0) tr[p].len1=max(tr[p].len1,tr[p<<1].r1+tr[p<<1|1].l1);
if(tr[p<<1].r0>0&&tr[p<<1|1].l0>0) tr[p].len0=max(tr[p].len0,tr[p<<1].r0+tr[p<<1|1].l0);
if(tr[p<<1].l1==tr[p<<1].len&&tr[p<<1|1].l1>0) tr[p].l1=tr[p<<1].l1+tr[p<<1|1].l1;
else tr[p].l1=tr[p<<1].l1;
if(tr[p<<1].l0==tr[p<<1].len&&tr[p<<1|1].l0>0) tr[p].l0=tr[p<<1].l0+tr[p<<1|1].l0;
else tr[p].l0=tr[p<<1].l0;
if(tr[p<<1|1].r1==tr[p<<1|1].len&&tr[p<<1].r1>0) tr[p].r1=tr[p<<1|1].r1+tr[p<<1].r1;
else tr[p].r1=tr[p<<1|1].r1;
if(tr[p<<1|1].r0==tr[p<<1|1].len&&tr[p<<1].r0>0) tr[p].r0=tr[p<<1|1].r0+tr[p<<1].r0;
else tr[p].r0=tr[p<<1|1].r0;
}
inline void down(int p){
int s=tr[p].l,t=tr[p].r,m=s+((t-s)>>1);
if(tr[p].add1==0){
tr[p<<1].sum=tr[p<<1].l1=tr[p<<1].r1=tr[p<<1].len1=0;
tr[p<<1].l0=tr[p<<1].r0=tr[p<<1].len0=(m-s+1);
tr[p<<1|1].sum=tr[p<<1|1].l1=tr[p<<1|1].r1=tr[p<<1|1].len1=0;
tr[p<<1|1].l0=tr[p<<1|1].r0=tr[p<<1|1].len0=(t-m);
tr[p<<1].add1=0;
tr[p<<1|1].add1=0;
tr[p].add1=-1;
tr[p<<1].add=tr[p<<1|1].add=tr[p].add=0;
}
else if(tr[p].add1==1){
tr[p<<1].sum=tr[p<<1].l1=tr[p<<1].r1=tr[p<<1].len1=(m-s+1);
tr[p<<1].l0=tr[p<<1].r0=tr[p<<1].len0=0;
tr[p<<1|1].sum=tr[p<<1|1].l1=tr[p<<1|1].r1=tr[p<<1|1].len1=(t-m);
tr[p<<1|1].l0=tr[p<<1|1].r0=tr[p<<1|1].len0=0;
tr[p<<1].add1=1;
tr[p<<1|1].add1=1;
tr[p].add1=-1;
tr[p<<1].add=tr[p<<1|1].add=tr[p].add=0;
}
if(tr[p].add){
tr[p<<1].sum=(m-s+1)-tr[p<<1].sum;
tr[p<<1|1].sum=(t-m)-tr[p<<1|1].sum;
if(tr[p<<1].add1!=-1) tr[p<<1].add1^=1;
else tr[p<<1].add^=1;
if(tr[p<<1|1].add1!=-1) tr[p<<1|1].add1^=1;
else tr[p<<1|1].add^=1;
swap(tr[p<<1].l1,tr[p<<1].l0);
swap(tr[p<<1].r1,tr[p<<1].r0);
swap(tr[p<<1].len1,tr[p<<1].len0);
swap(tr[p<<1|1].l1,tr[p<<1|1].l0);
swap(tr[p<<1|1].r1,tr[p<<1|1].r0);
swap(tr[p<<1|1].len1,tr[p<<1|1].len0);
tr[p].add=0;
}
}
inline void build(int l,int r,int p){
tr[p].add1=-1;
tr[p].len=(r-l+1);
tr[p].l=l,tr[p].r=r;
if(l==r){
if(a[l]) tr[p].sum=tr[p].len1=tr[p].l1=tr[p].r1=tr[p].len,tr[p].l0=tr[p].r0=tr[p].len0=0;
else tr[p].sum=tr[p].len1=tr[p].l1=tr[p].r1=0,tr[p].l0=tr[p].r0=tr[p].len0=tr[p].len;
return;
}
int m=l+((r-l)>>1);
build(l,m,p<<1);
build(m+1,r,p<<1|1);
up(p);
}
inline void change_0(int l,int r,int s,int t,int p){
if(l<=s&&r>=t){
tr[p].sum=tr[p].l1=tr[p].r1=tr[p].len1=0;
tr[p].l0=tr[p].r0=tr[p].len0=tr[p].len;
tr[p].add1=0;
return;
}
down(p);
int m=s+((t-s)>>1);
if(l<=m) change_0(l,r,s,m,p<<1);
if(r>m) change_0(l,r,m+1,t,p<<1|1);
up(p);
}
inline void change_1(int l,int r,int s,int t,int p){
if(l<=s&&r>=t){
tr[p].sum=tr[p].l1=tr[p].r1=tr[p].len1=tr[p].len;
tr[p].l0=tr[p].r0=tr[p].len0=0;
tr[p].add1=1;
return;
}
down(p);
int m=s+((t-s)>>1);
if(l<=m) change_1(l,r,s,m,p<<1);
if(r>m) change_1(l,r,m+1,t,p<<1|1);
up(p);
}
inline void change_swap(int l,int r,int s,int t,int p){
if(l<=s&&r>=t){
tr[p].sum=tr[p].len-tr[p].sum;
swap(tr[p].l1,tr[p].l0);
swap(tr[p].r1,tr[p].r0);
swap(tr[p].len1,tr[p].len0);
tr[p].add^=1;
return;
}
down(p);
int m=s+((t-s)>>1);
if(l<=m) change_swap(l,r,s,m,p<<1);
if(r>m) change_swap(l,r,m+1,t,p<<1|1);
up(p);
}
inline int query_sum(int l,int r,int s,int t,int p){
if(l<=s&&r>=t) return tr[p].sum;
down(p);
int m=s+((t-s)>>1),res=0;
if(l<=m) res+=query_sum(l,r,s,m,p<<1);
if(r>m) res+=query_sum(l,r,m+1,t,p<<1|1);
return res;
}
inline node query_len(int l,int r,int p){
if(tr[p].l==l&&tr[p].r==r) return tr[p];
down(p);
int m=tr[p].l+((tr[p].r-tr[p].l)>>1);
if(m<l) return query_len(l,r,p<<1|1);
else if(m>=r) return query_len(l,r,p<<1);
else{
node L=query_len(l,m,p<<1),R=query_len(m+1,r,p<<1|1),res;
res.sum=L.sum+R.sum;
if(L.sum==L.len) res.l1=L.len+R.l1;
else res.l1=L.l1;
if(L.sum==0) res.l0=L.len+R.l0;
else res.l0=L.l0;
if(R.sum==R.len) res.r1=L.r1+R.len;
else res.r1=R.r1;
if(R.sum==0) res.r0=L.r0+R.len;
else res.r0=R.r0;
res.len1=L.r1+R.l1;
res.len0=L.r0+R.l0;
res.len1=max(max(L.len1,R.len1),res.len1);
res.len0=max(max(L.len0,R.len0),res.len0);
return res;
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>Q;
for(re int i=1;i<=n;++i) cin>>a[i];
build(1,n,1);
while(Q--){
int op,x,y;
cin>>op>>x>>y;
x++,y++;
if(op==0) change_0(x,y,1,n,1);//cout<<"change_0"<<'\n';
if(op==1) change_1(x,y,1,n,1);//cout<<"change_1"<<'\n';
if(op==2) change_swap(x,y,1,n,1);//cout<<"change_swap"<<'\n';
if(op==3){
//int po=query_sum(x,y,1,n,1);
//cout<<"sum"<<'\n';
cout<<query_sum(x,y,1,n,1)<<'\n';
}
if(op==4){
//int po=query_len(x,y,1,n,1);
//cout<<"len"<<'\n';
cout<<query_len(x,y,1).len1<<'\n';
}
// cout<<x<<" "<<y<<" "<<'\n';
// if(op==3) cout<<"ans="<<query_sum(x,y,1,n,1);
// if(op==4) cout<<"ans="<<query_len(x,y,1,n,1).len1;
// cout<<'\n';
// for(re int i=1;i<=n;++i) cout<<query_sum(i,i,1,n,1)<<" ";
// cout<<'\n';
}
//for(re int i=1;i<=n*n;++i) cout<<tr[i].len<<" "<<tr[i].len1<<" "<<tr[i].l1<<" "<<tr[i].r1<<'\n';
return 0;
}