泡泡堂
\(solution\)
苹果树
\(solution\)
字符合并
\(solution\)
脑洞治疗仪
\(solution\)
万万没想到，我50pts的原因是数组没开够
线段树维护修改操作，注意先挖后补
AC Code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=2e5+5;
int n,m;
struct ww{
int l,r,sum,lm,rm,len;
int dat,tag;
}tr[N*8];
void updat(int p)
{
tr[p].sum=max(max(tr[p<<1].sum,tr[p<<1|1].sum),tr[p<<1].rm+tr[p<<1|1].lm);
tr[p].dat=tr[p<<1].dat+tr[p<<1|1].dat;
if(tr[p<<1].sum==tr[p<<1].len)
{
tr[p].lm=tr[p<<1].len+tr[p<<1|1].lm;
}
else tr[p].lm=tr[p<<1].lm;
if(tr[p<<1|1].sum==tr[p<<1|1].len)
{
tr[p].rm=tr[p<<1|1].len+tr[p<<1].rm;
}
else tr[p].rm=tr[p<<1|1].rm;
}
void build(int p,int l,int r)
{
tr[p].l=l,tr[p].r=r;
tr[p].len=r-l+1;
if(l==r)return ;
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
updat(p);
}
void pushdown(int p)
{
if(tr[p].tag==1)
{
tr[p<<1].tag=1;
tr[p<<1].sum=tr[p<<1].lm=tr[p<<1].rm=tr[p<<1].dat=tr[p<<1].len;
tr[p<<1|1].tag=1;
tr[p<<1|1].sum=tr[p<<1|1].lm=tr[p<<1|1].rm=tr[p<<1|1].dat=tr[p<<1|1].len;
tr[p].tag=0;
}
if(tr[p].tag==2)
{
tr[p<<1].tag=2;
tr[p<<1].sum=tr[p<<1].lm=tr[p<<1].rm=tr[p<<1].dat=0;
tr[p<<1|1].tag=2;
tr[p<<1|1].sum=tr[p<<1|1].lm=tr[p<<1|1].rm=tr[p<<1|1].dat=0;
tr[p].tag=0;
}
}
void change1(int p,int l,int r)
{
int l1=tr[p].l,r1=tr[p].r;
if(r1<l||r<l1)return ;
if(l<=l1&&r1<=r)
{
pushdown(p);
tr[p].tag=1;
tr[p].sum=tr[p].lm=tr[p].rm=tr[p].dat=tr[p].len;
return ;
}
pushdown(p);
int mid=(l1+r1)>>1;
if(l<=mid)change1(p<<1,l,r);
if(r>mid)change1(p<<1|1,l,r);
updat(p);
}
ww ask1(int p,int l,int r)
{
int l1=tr[p].l,r1=tr[p].r;
if(l<=l1&&r1<=r)
{
pushdown(p);
return tr[p];
}
pushdown(p);
ww ans,tr1,tr2;
int o1=0,o2=0;
int mid=(l1+r1)>>1;
if(l<=mid)
{
tr1=ask1(p<<1,l,r);
o1=1;
}
if(r>mid)
{
tr2=ask1(p<<1|1,l,r);
o2=1;
}
updat(p);
if(o1==0)return tr2;
if(o2==0)return tr1;
ans.sum=max(max(tr1.sum,tr2.sum),tr1.rm+tr2.lm);
ans.len=tr1.len+tr2.len;
if(tr1.sum==tr1.len)
{
ans.lm=tr1.len+tr2.lm;
}
else ans.lm=tr1.lm;
if(tr2.sum==tr2.len)
{
ans.rm=tr2.len+tr1.rm;
}
else ans.rm=tr2.rm;
return ans;
}
int ask2(int p,int l,int r)
{
int l1=tr[p].l,r1=tr[p].r;
if(r1<l||r<l1)return 0;
if(l<=l1&&r1<=r)
{
pushdown(p);
return tr[p].dat;
}
pushdown(p);
int ans=0;
int mid=(l1+r1)>>1;
if(l<=mid)ans+=ask2(p<<1,l,r);
if(r>mid)ans+=ask2(p<<1|1,l,r);
updat(p);
return ans;
}
int dat1;
void change2(int p,int l,int r)
{
int l1=tr[p].l,r1=tr[p].r;
if(r1<l||r<l1)return ;
if(dat1==0)return ;
if(l<=l1&&r1<=r&&tr[p].dat<=dat1)
{
dat1-=tr[p].dat;
pushdown(p);
tr[p].tag=2;
tr[p].sum=tr[p].dat=tr[p].lm=tr[p].rm=0;
return ;
}
pushdown(p);
int mid=(l1+r1)>>1;
if(l<=mid)change2(p<<1,l,r);
if(r>mid)change2(p<<1|1,l,r);
updat(p);
}
int main()
{
// freopen("head.in","r",stdin);
// freopen("head.out","w",stdout);
n=read(),m=read();
int opt,l,r;
build(1,1,n);
for(int i=1;i<=m;i++)
{
opt=read(),l=read(),r=read();
if(opt==0)
{
change1(1,l,r);
}
else if(opt==1)
{
int l1,r1;
l1=read(),r1=read();
dat1=r-l+1-ask2(1,l,r);
change1(1,l,r);
change2(1,l1,r1);
}
else
{
int tmp=ask1(1,l,r).sum;
printf("%d\n",tmp);
}
}
return 0;
}