lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？
线段树代码题
维护最左边，最右边区间内最长连续0，1的个数
异或的时候交换一下0，1的信息就好
感觉就是如果你不能快速统计出一个元素的信息，你就维护一些可以合并的信息，然后快速合并
比如这个0，1，如果你不维护连续0，那么异或以后你是无法快速统计出异或后的连续1的答案的
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
const int N = 101100;
int a[N],n,m;
int sum[N<<2];
int cov_1[N<<2],cov_2[N<<2];//_1维护把区间全部变成某个数，_2维护把区间取反
int ln[N<<2],rn[N<<2],mn[N<<2];
int l0[N<<2],r0[N<<2],m0[N<<2];//应对取反操作。。
int max=-1;
inline int pushup(int cur,int x){
sum[cur]=sum[cur<<1]+sum[cur<<1|1];
if(sum[cur<<1]==(x+1>>1)){ln[cur]=sum[cur<<1]+ln[cur<<1|1];l0[cur]=0; }//左叶子全为1
else{ln[cur]=ln[cur<<1];}
if(sum[cur<<1|1]==(x>>1)){rn[cur]=sum[cur<<1|1]+rn[cur<<1];r0[cur]=0;}
else{rn[cur]=rn[cur<<1|1],r0[cur]=r0[cur<<1|1];}
if(sum[cur<<1]==0){l0[cur]=((x+1)>>1)+l0[cur<<1|1];ln[cur]=0;}
else{l0[cur]=l0[cur<<1];}
if(sum[cur<<1|1]==0){r0[cur]=(x>>1)+r0[cur<<1];rn[cur]=0;}
else{r0[cur]=r0[cur<<1|1];}
mn[cur]=std::max(mn[cur<<1],std::max(mn[cur<<1|1],rn[cur<<1]+ln[cur<<1|1]));
m0[cur]=std::max(m0[cur<<1],std::max(m0[cur<<1|1],r0[cur<<1]+l0[cur<<1|1]));
}
//对一个操作先修改再取反
inline int pushdown(int cur,int x){
if(cov_1[cur]!=-1){
cov_1[cur<<1]=cov_1[cur];
cov_1[cur<<1|1]=cov_1[cur];
cov_2[cur<<1]=0;
cov_2[cur<<1|1]=0;
sum[cur<<1]=(x+1>>1)*cov_1[cur];
sum[cur<<1|1]=(x>>1)*cov_1[cur];
ln[cur<<1]=rn[cur<<1]=mn[cur<<1]=(x+1>>1)*cov_1[cur];
l0[cur<<1]=r0[cur<<1]=m0[cur<<1]=(x+1>>1)-ln[cur<<1];
ln[cur<<1|1]=rn[cur<<1|1]=mn[cur<<1|1]=(x>>1)*cov_1[cur];
l0[cur<<1|1]=r0[cur<<1|1]=m0[cur<<1|1]=(x>>1)-rn[cur<<1|1];
cov_1[cur]=-1;
}
if(cov_2[cur]){
if(cov_2[cur<<1]==-1) cov_2[cur<<1]=1;
if(cov_2[cur<<1|1]==-1) cov_2[cur<<1|1]=1;
cov_2[cur<<1]^=1;
cov_2[cur<<1|1]^=1;
sum[cur<<1]=(x+1>>1)-sum[cur<<1];
sum[cur<<1|1]=(x>>1)-sum[cur<<1|1];
std::swap(ln[cur<<1],l0[cur<<1]);std::swap(ln[cur<<1|1],l0[cur<<1|1]);
std::swap(rn[cur<<1],r0[cur<<1]);std::swap(rn[cur<<1|1],r0[cur<<1|1]);
std::swap(mn[cur<<1],m0[cur<<1]);std::swap(mn[cur<<1|1],m0[cur<<1|1]);
cov_2[cur]=0;
}
}
void cancel(int l,int r,int cur){
if(r==l) return ;
cov_2[cur]=0;
int mid=l+r>>1;
cancel(l,mid,cur<<1);
cancel(mid+1,r,cur<<1|1);
}
inline int change(int l,int r,int L,int R,int cur,int od){
if(L<=l&&r<=R){
if(od!=2){
sum[cur]=(r-l+1)*od;
ln[cur]=rn[cur]=mn[cur]=od*(r-l+1);
l0[cur]=r0[cur]=m0[cur]=r-l+1-ln[cur];
cov_1[cur]=od;
cov_2[cur]=0;
//cancel(l,r,cur);
}
if(od==2){
sum[cur]=r-l+1-sum[cur];
std::swap(ln[cur],l0[cur]);
std::swap(rn[cur],r0[cur]);
std::swap(mn[cur],m0[cur]);
cov_2[cur]^=1;
}
return 0;
}
pushdown(cur,r-l+1);
int mid = l+r>>1;
if(L<=mid) change(l,mid,L,R,cur<<1,od);
if(R>mid) change(mid+1,r,L,R,cur<<1|1,od);
pushup(cur,r-l+1);
return 0;
}
inline int ask(int l,int r,int L,int R,int cur,int od){
if(L<=l&&r<=R){
if(od==3){
return sum[cur];
}
if(od==4){
max=std::max(max,mn[cur]);
return mn[cur];
}
return 0;
}
pushdown(cur,r-l+1);
int mid = l+r>>1,ans=0;
if(od==4){
max=std::max(std::min(mid-L+1,rn[cur<<1])+std::min(R-mid,ln[cur<<1|1]),max);
}
if(L<=mid) ans+=ask(l,mid,L,R,cur<<1,od);
if(R>mid) ans+=ask(mid+1,r,L,R,cur<<1|1,od);
return ans;
}
inline int build(int l,int r,int cur){
if(l==r){
sum[cur]=a[l];
mn[cur]=ln[cur]=rn[cur]=a[l];
l0[cur]=r0[cur]=m0[cur]=1-a[l];
return 0;
}
int mid = l+r>>1;
build(l,mid,cur<<1);
build(mid+1,r,cur<<1|1);
pushup(cur,r-l+1);
return 0 ;
}
int main (){
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
memset(cov_1,-1,sizeof(cov_1));
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;++i){
scanf("%d",&a[i]);
}
build(1,n,1);
while(m--){
int od,l,r;
scanf("%d %d %d",&od,&l,&r);
l++,r++;
if(l>r) std::swap(l,r);
if(od>=0&&od<=2){
change(1,n,l,r,1,od);
}
else{
max=-1;
int ans = ask(1,n,l,r,1,od);
if(od==4)ans=max;
printf("%d\n",ans);
}// for(int i=1;i<=n;++i)
// printf("%d",ask(1,n,i,i,1,3)); printf("\n");
}
return 0;
}
0 条评论