嗯，毒瘤数据结构毁青春。。。
scoi不愧是数据结构专场，尽出一些毒瘤题。。。。
一眼可以看出线段树，题意很好理解，思路很好想，可TM就是打不对！！！
打代码一小时，debug一整天，我能说什么。。
区间1的个数(sum)，这个太裸就不说了。
区间连续的1的个数，经典的连续区间问题，无非就是维护每个区间区间左边连续的1的个数(lsum),右边连续的1的个数(rsum)，区间最长连续的1的个数(maxsum)。。。
然后就没有然后了。。。修改更新查询什么的。。
写这篇blog主要是为了提醒自己：lazy表示当前区间已被修改，但子区间没有。
记着记着就记混了，然后一整天疯狂GG。
然后直接上代码吧。
(p.为了方便，我把区间编号和操作序数全部+1，所以opt在[1,5],序列在[1,n]。)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define gch getchar
#define pch putchar
#define LL long long
#define INF 0xfffffff
#define ls (now<<1)
#define rs (now<<1|1)
using namespace std;
template <class X> inline void read(X &x){
char c=getchar();x=0;X flag=1;
while(c>'9'||c<'0') {if(c=='-') flag=-1;c=getchar();}
while(c<='9'&&c>='0') {x=x*10+c-48;c=getchar();}
x*=flag;
}
const int MAXN=100000+5;
int n,m,a[MAXN];
struct Segment_Tree{
int lazy,l,r,num;
int sum[2],lsum[2],rsum[2],maxsum[2];
//二维数组，分别表示0,1的各种情况，其实完全没有必要记录这么多，但我觉得这么写很爽啊。。。
}tree[MAXN<<2];
inline int all(int now,int k){//当前区间是否全部为K。
return tree[now].sum[k]==tree[now].num;
}
inline void pushup(int now){
for(int i=0;i<=1;++i){
tree[now].maxsum[i]=max(tree[ls].rsum[i]+tree[rs].lsum[i],max(tree[ls].maxsum[i],tree[rs].maxsum[i]));
if(all(ls,i)) tree[now].lsum[i]=tree[ls].num+tree[rs].lsum[i];
else tree[now].lsum[i]=tree[ls].lsum[i];
if(all(rs,i)) tree[now].rsum[i]=tree[rs].num+tree[ls].rsum[i];
else tree[now].rsum[i]=tree[rs].rsum[i];
tree[now].sum[i]=tree[ls].sum[i]+tree[rs].sum[i];
}
}
inline void build(int now,int l,int r){
tree[now].l=l;tree[now].r=r;
tree[now].num=r-l+1;tree[now].lazy=0;
if(l==r){
int k=a[l];
tree[now].maxsum[k]=tree[now].lsum[k]=tree[now].rsum[k]=tree[now].sum[k]=1;
tree[now].maxsum[k^1]=tree[now].lsum[k^1]=tree[now].rsum[k^1]=tree[now].sum[k^1]=0;
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(now);
}
inline void change(int now,int opt){
switch(opt){
case 1:{
tree[now].maxsum[0]=tree[now].sum[0]=tree[now].lsum[0]=tree[now].rsum[0]=tree[now].num;
tree[now].maxsum[1]=tree[now].sum[1]=tree[now].lsum[1]=tree[now].rsum[1]=0;
break;
}
case 2:{
tree[now].maxsum[0]=tree[now].sum[0]=tree[now].lsum[0]=tree[now].rsum[0]=0;
tree[now].maxsum[1]=tree[now].sum[1]=tree[now].lsum[1]=tree[now].rsum[1]=tree[now].num;
break;
}
case 3:{
swap(tree[now].maxsum[0],tree[now].maxsum[1]);
swap(tree[now].sum[0],tree[now].sum[1]);
swap(tree[now].lsum[0],tree[now].lsum[1]);
swap(tree[now].rsum[0],tree[now].rsum[1]);
break;
}
default:{
break;
}
}
}
inline void mark(int now,int opt){//打lazy标记，注意2操作不能直接覆盖，0,1操作可以。
if(opt==1 || opt==2){
change(now,opt);
tree[now].lazy=opt;
}
else {
if(tree[now].lazy==0) change(now,3),tree[now].lazy=3;
else if(tree[now].lazy==3) change(now,3),tree[now].lazy=0;
else if(tree[now].lazy==1) change(now,2),tree[now].lazy=2;
else if(tree[now].lazy==2) change(now,1),tree[now].lazy=1;
}
}
inline void pushdown(int now){
mark(ls,tree[now].lazy);
mark(rs,tree[now].lazy);
tree[now].lazy=0;
}
inline void operate(int now,int L,int R,int opt){
int l=tree[now].l,r=tree[now].r;
if(L<=l && r<=R){
mark(now,opt);
return;
}
if(tree[now].lazy!=0) pushdown(now);
int mid=(l+r)>>1;
if(L<=mid) operate(ls,L,R,opt);
if(R>mid) operate(rs,L,R,opt);
pushup(now);
}
inline int query1(int now,int L,int R){//查询1的个数。
int l=tree[now].l,r=tree[now].r;
if(L<=l && r<=R){
return tree[now].sum[1];
}
if(tree[now].lazy!=0) pushdown(now);
int ans=0;
int mid=(l+r)>>1;
if(L<=mid) ans+=query1(ls,L,R);
if(R>mid) ans+=query1(rs,L,R);
return ans;
}
//tot表示整块区间都是1,与all同理。
inline void query2(int now,int L,int R,int &max_lsum,int &max_rsum,int &max_ans,bool &tot){//区间连续的1。
int l=tree[now].l,r=tree[now].r;
if(L<=l && r<=R){
max_rsum=tree[now].rsum[1];
max_lsum=tree[now].lsum[1];
max_ans=tree[now].maxsum[1];
tot=all(now,1);
return;
}
if(tree[now].lazy!=0) pushdown(now);
int mid=(l+r)>>1;
if(L<=mid && R>mid){
int a,b,c;bool d;
int e,f,g;bool h;
query2(ls,L,R,a/*lsum*/,b/*rsum*/,c/*max_sum*/,d/*tot*/);
query2(rs,L,R,e/*lsum*/,f/*rsum*/,g/*max_sum*/,h/*tot*/);
if(d) max_lsum=a+e;else max_lsum=a;
if(h) max_rsum=b+f;else max_rsum=f;
max_ans=max(max(c,g),b+e);
tot=d && h;
}
else if(R<=mid){
query2(ls,L,R,max_lsum,max_rsum,max_ans,tot);
}
else if(L>mid){
query2(rs,L,R,max_lsum,max_rsum,max_ans,tot);
}
}
inline void print_tree(int now){//输出整棵线段树，现在你能想象我debug的艰辛了吗。。(为了简洁，已省去其他输出中间变量，这个就当做纪念吧。。)
int l=tree[now].l,r=tree[now].r;
printf("now:%d l:%d r:%d num:%d lazy:%d
",now,tree[now].l,tree[now].r,tree[now].num,tree[now].lazy);
for(int i=0;i<=1;++i){
printf("i:%d sum:%d maxsum:%d lsum:%d rsum:%d
",i,tree[now].sum[i],tree[now].maxsum[i],tree[now].lsum[i],tree[now].rsum[i]);
}
printf("
");
if(l==r) return;
int mid=(l+r)>>1;
print_tree(ls);
print_tree(rs);
}
int main(){
read(n);read(m);
for(int i=1;i<=n;++i) read(a[i]);
build(1,1,n);
for(int i=1;i<=m;++i){
int opt,l,r;
read(opt);read(l);read(r);
opt++;l++;r++;
if(opt>=1 && opt<=3) operate(1,l,r,opt);
else if(opt==4) printf("%d
",query1(1,l,r));
else if(opt==5){
int a,b,c;bool d=0;
query2(1,l,r,a,b,c,d);
printf("%d
",c);
}
}
return 0;
}