P4344 [SHOI2015] 脑洞治疗仪 线段树+二分

主要是维护一个连续区间，比较经典的题目，还要考虑一下二分的情况，否则很难处理，比较有难度。这里和序列操作一题的区别是不需要考虑1的个数，因为不需要取反。
传送门https://www.luogu.com.cn/problem/P4344

#include<iostream>
using namespace std;
#define lc u<<1
#define rc u<<1|1
const int N=2e5+10;
struct Tree{int l,r;int a,la,ra,ma;//  0的个数  左连续 右连续 总连续int len,add;
}tr[N*4];//
int n,m;void mo(int u,int k){Tree &t=tr[u];if(k==0){t.a=t.la=t.ra=t.ma=t.len;t.add=0;}if(k==1){t.a=t.la=t.ra=t.ma=0;t.add=1;}
}void pushdown(int u){Tree &t=tr[u];if(t.add==0) mo(lc,0),mo(rc,0);if(t.add==1) mo(lc,1),mo(rc,1);t.add=-1;
}void pushup(Tree &t,Tree l,Tree r){t.a=l.a+r.a;t.la=((l.a==l.len) ? l.la+r.la : l.la); t.ra=((r.a==r.len) ? r.ra+l.ra : r.ra);t.ma=max(max(l.ma,r.ma),l.ra+r.la);
}void build(int u,int l,int r){tr[u]={l,r,0,0,0,0,r-l+1,-1};if(l==r) return;int m=(l+r)>>1;build(lc,l,m);build(rc,m+1,r);pushup(tr[u],tr[lc],tr[rc]);
}void update(int u,int l,int r,int k){if(l<=tr[u].l&&tr[u].r<=r){mo(u,k);return;}pushdown(u);int m=(tr[u].l+tr[u].r)>>1;if(l<=m) update(lc,l,r,k);if(r>m) update(rc,l,r,k);pushup(tr[u],tr[lc],tr[rc]);
}Tree query0(int u,int l,int r){if(l<=tr[u].l&&tr[u].r<=r){return tr[u];}pushdown(u);int m=(tr[u].l+tr[u].r)>>1;if(r<=m) return query0(lc,l,r);if(l>m) return query0(rc,l,r);Tree t;pushup(t,query0(lc,l,m),query0(rc,m+1,r));return t;
}int query0sum(int u,int l,int r){if(l<=tr[u].l&&tr[u].r<=r){return tr[u].a;}pushdown(u);int ans=0;int m=(tr[u].l+tr[u].r)>>1;if(l<=m) ans+=query0sum(lc,l,r);if(r>m) ans+=query0sum(rc,l,r);return ans;
}int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;build(1,1,n);while(m--){int op,x1,y1;cin>>op>>x1>>y1;if(op==0) update(1,x1,y1,0);if(op==1){int x2,y2;cin>>x2>>y2;int x=(y1-x1+1)-query0sum(1,x1,y1);//1的个数update(1,x1,y1,0);int l=x2-1,r=y2+1;//二分if(x==0) continue;while(l+1<r){int mid=(l+r)>>1;if(query0sum(1,x2,mid)<=x) l=mid;else r=mid;}update(1,x2,l,1);}	if(op==2) cout<<query0(1,x1,y1).ma<<endl;	}return 0;
}