LGP4344 [SHTS 2015] 脑洞治疗仪
Luogu Link
题意简述
给定一个 \(\texttt{01}\) 序列。三种操作：
0 l r：将区间 \([l,r]\) 全部设为 \(0\)。1 l0 r0 l1 r1：将区间 \([l_0,r_0]\) 中的 \(1\) 全部挖出来，从左到右尽量填充 \([l_1,r_1]\)，多余的 \(1\) 丢掉。2 l r：询问最大的连续 \(0\) 段的长度。
做法解析
线段树。显然就是覆盖标签和最大子段相结合的题目。不赘述。
代码实现
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=2e5+5;
int N,M,Opt,X[2],Y[2],A[MaxN];
struct anob{int l,r,t;};
struct SegTree{int cl[MaxN<<2],cr[MaxN<<2],cmid[MaxN<<2],clen[MaxN<<2];int lzmx[MaxN<<2],rzmx[MaxN<<2],tzmx[MaxN<<2],osum[MaxN<<2],tag[MaxN<<2];int ls(int u){return u<<1;}int rs(int u){return (u<<1)|1;}void pushup(int u){lzmx[u]=lzmx[ls(u)]+(lzmx[ls(u)]==clen[ls(u)])*lzmx[rs(u)];rzmx[u]=rzmx[rs(u)]+(rzmx[rs(u)]==clen[rs(u)])*rzmx[ls(u)];tzmx[u]=max({tzmx[ls(u)],tzmx[rs(u)],rzmx[ls(u)]+lzmx[rs(u)]}),osum[u]=osum[ls(u)]+osum[rs(u)];}void build(int u,int l,int r){cl[u]=l,cr[u]=r,clen[u]=r-l+1,tag[u]=-1;if(l==r){osum[u]=A[l],lzmx[u]=rzmx[u]=tzmx[u]=!A[l];return;}int mid=(l+r)>>1;cmid[u]=mid;build(ls(u),l,mid),build(rs(u),mid+1,r),pushup(u);}void maketag(int u,int x){tag[u]=x;if(x==0)lzmx[u]=rzmx[u]=tzmx[u]=clen[u],osum[u]=0;if(x==1)lzmx[u]=rzmx[u]=tzmx[u]=0,osum[u]=clen[u];}void pushdown(int u){if(tag[u]==-1)return;maketag(ls(u),tag[u]),maketag(rs(u),tag[u]),tag[u]=-1;}int digupd(int u,int dl,int dr){int res=0;if(dl<=cl[u]&&cr[u]<=dr){int tmp=osum[u];maketag(u,0);return tmp;}pushdown(u);if(dl<=cmid[u])res+=digupd(ls(u),dl,dr);if(dr>cmid[u])res+=digupd(rs(u),dl,dr);pushup(u);return res;}int filupd(int u,int dl,int dr,int x){if(!x)return 0;if(dl<=cl[u]&&cr[u]<=dr){int ntf=clen[u]-osum[u];if(ntf<=x){maketag(u,1);return x-ntf;}}pushdown(u);if(dl<=cmid[u])x=filupd(ls(u),dl,dr,x);if(dr>cmid[u])x=filupd(rs(u),dl,dr,x);pushup(u);return x;}anob gettzmx(int u,int dl,int dr){if(dl<=cl[u]&&cr[u]<=dr)return {lzmx[u],rzmx[u],tzmx[u]};anob cres,lres={0,0,0},rres={0,0,0};pushdown(u);if(dl<=cmid[u])lres=gettzmx(ls(u),dl,dr);if(dr>cmid[u])rres=gettzmx(rs(u),dl,dr);cres.l=lres.l+(lres.l==cmid[u]-max(dl,cl[u])+1)*rres.l;cres.r=rres.r+(rres.r==min(cr[u],dr)-cmid[u])*lres.r;cres.t=max({lres.t,rres.t,lres.r+rres.l});return cres;}
}SgT;
int main(){readis(N,M);for(int i=1;i<=N;i++)A[i]=1;SgT.build(1,1,N);for(int i=1;i<=M;i++){readis(Opt,X[0],Y[0]);if(Opt==0)SgT.digupd(1,X[0],Y[0]);if(Opt==1){readis(X[1],Y[1]);int tmp=SgT.digupd(1,X[0],Y[0]);SgT.filupd(1,X[1],Y[1],tmp);}if(Opt==2)writil(SgT.gettzmx(1,X[0],Y[0]).t);}return 0;
}