1858: [Scoi2010]序列操作
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 3213 Solved: 1548
[Submit][Status][Discuss]
Description
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都需要给出回答，聪明的程序员们，你们能帮助他吗？
Input
输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目 第二行包括n个数，表示序列的初始状态 接下来m行，每行3个数，op, a, b，（0 < = op < = 4，0 < = a < = b）
Output
对于每一个询问操作，输出一行，包括1个数，表示其对应的答案
Sample Input
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
Sample Output
5
2
6
5
2
6
5
HINT
对于30%的数据，1<=n, m<=1000 对于100%的数据，1< = n, m < = 100000
Source
线段树大合集，头脑清醒就行了2333
唯一需要注意的一点是，我们对节点修改的时候，需要讨论翻转和覆盖的关系，这里我就不剧透了，你们自己想吧2333
#include<bits/stdc++.h>
#define ll long long
#define maxn 400005
using namespace std;
int mxl[maxn][2],mxr[maxn][2];
int mx[maxn][2],tag[maxn],sum[maxn];
int n,m,a[maxn],le,ri,w,opt,qz,ans;
inline void maintain(int o,int l,int r){
int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1;
sum[o]=sum[lc]+sum[rc];
if(sum[lc]==mid-l+1) mxl[o][1]=sum[lc]+mxl[rc][1],mxl[o][0]=0;
else if(!sum[lc]) mxl[o][0]=mid-l+1+mxl[rc][0],mxl[o][1]=0;
else mxl[o][0]=mxl[lc][0],mxl[o][1]=mxl[lc][1];
if(sum[rc]==r-mid) mxr[o][1]=sum[rc]+mxr[lc][1],mxr[o][0]=0;
else if(!sum[rc]) mxr[o][0]=r-mid+mxr[lc][0],mxr[o][1]=0;
else mxr[o][0]=mxr[rc][0],mxr[o][1]=mxr[rc][1];
mx[o][0]=max(mx[lc][0],max(mx[rc][0],mxr[lc][0]+mxl[rc][0]));
mx[o][1]=max(mx[lc][1],max(mx[rc][1],mxr[lc][1]+mxl[rc][1]));
}
inline void change(int o,int l,int r,int TO){
if(TO<=2) tag[o]=TO;
else{
if(tag[o]&&tag[o]<=2) tag[o]=3-tag[o];
else{
tag[o]=3-tag[o];
sum[o]=r-l+1-sum[o];
swap(mx[o][0],mx[o][1]);
swap(mxl[o][0],mxl[o][1]);
swap(mxr[o][0],mxr[o][1]);
}
}
if(tag[o]==1){
sum[o]=mx[o][1]=mxl[o][1]=mxr[o][1]=0;
mxl[o][0]=mx[o][0]=mxr[o][0]=r-l+1;
}
else if(tag[o]==2){
sum[o]=mx[o][1]=mxl[o][1]=mxr[o][1]=r-l+1;
mxl[o][0]=mx[o][0]=mxr[o][0]=0;
}
}
inline void pushdown(int o,int l,int r){
int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1;
if(tag[o]){
change(lc,l,mid,tag[o]);
change(rc,mid+1,r,tag[o]);
tag[o]=0;
}
}
void build(int o,int l,int r){
if(l==r){
mx[o][a[l]]=mxl[o][a[l]]=mxr[o][a[l]]=1;
sum[o]=a[l];
return;
}
int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1;
build(lc,l,mid),build(rc,mid+1,r);
maintain(o,l,r);
}
void update(int o,int l,int r){
if(l>=le&&r<=ri){
change(o,l,r,opt);
return;
}
int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1;
pushdown(o,l,r);
if(le<=mid) update(lc,l,mid);
if(ri>mid) update(rc,mid+1,r);
maintain(o,l,r);
}
int querysum(int o,int l,int r){
if(l>=le&&r<=ri) return sum[o];
int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1,an=0;
pushdown(o,l,r);
if(le<=mid) an+=querysum(lc,l,mid);
if(ri>mid) an+=querysum(rc,mid+1,r);
return an;
}
void query_continue(int o,int l,int r){
if(l>=le&&r<=ri){
ans=max(ans,max(mx[o][1],qz+mxl[o][1]));
if(sum[o]==r-l+1) qz+=sum[o];
else qz=mxr[o][1];
return;
}
int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1;
pushdown(o,l,r);
if(le<=mid) query_continue(lc,l,mid);
if(ri>mid) query_continue(rc,mid+1,r);
}
inline void solve(){
while(m--){
scanf("%d%d%d",&opt,&le,&ri),le++,ri++;
if(opt<=2){
opt++;
update(1,1,n);
}
else if(opt==3) printf("%d
",querysum(1,1,n));
else{
qz=ans=0;
query_continue(1,1,n);
printf("%d
",ans);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",a+i);
build(1,1,n);
solve();
return 0;
}