正解:线段树+二分答案/分块
解题报告:
懒得写题目描述辣,放个传送门qwq
首先线段树是很容易想到的?区间修改嘛
然后,操作1就是模板嘛,有一定难度的在于操作2和3(其实是012,不管,强行做123x
那操作23怎么实现呢?
二分
完
还是有点难度的对我来说,所以都说下趴$QAQ$
- 首先操作2,我们可以先分别求下用来填充的区间和被填充的区间的1的数量,如果用来填充的1的数量>我们要填充的那块儿的总数-被填充的1的数量(也就是要填的0的数量嘛$quq$,那我们就可以直接填上去,和直接的区间修改没有差别
那如果小于怎么搞?
二分
好滴讲完了,完
实在懒得讲下去了,,,但是觉得$gql$这么蠢再看一遍不一定能理解啊,,,还是再港下?
就从前往后找1,二分地搞,然后找到1的那段都可以跳过,于是就一直加一直加一直加,最后就好了
- 关于操作3,类似,只是会变成取max,同样是二分找到一直为0的一段区间嘛,然后就完?
大概能懂趴?
然后,我发现我脑子不太好,,,我不知道为啥突然脑子一抽就觉得,我好像这题没写题解?于是就又写了篇,,,于是我就把那篇删了,然后因为表述有点儿不一样所以还是把那篇的表述搬过来好了$qwq$
首先建棵线段树,存这段区间内所有1的个数
港最简单的操作,就是那个0$lr$.相当于就$lr$都变成0,没什么可说的嗷,基本操作$qwq$
然后1和2的操作想法都是类似的,分别港下趴还是qwq
首先对于操作$1\ l_{0}\ r_{0}\ l_{1}\ r_{1}$,$l_{0}$到$r_{0}$肯定可以直接赋值0了不解释
首先如果$l_{0}$到$r_{0}$中1的数量是大于$l_{0}$到$r_{0}$中0的数量就直接让$l_{1}$到$r_{1}$赋值为1就成了,不需要别的操作了,依然基本操作呢
但是如果小于,思考怎么做
肯定是从前往后跑能补就补就是了,那怎么看能不能补呢,首先我们肯定要先定位到第一个是0的点
这个可以用$query$直接求下判断是否是1,然后如果是1就二分查找找到第一个是0的点(关于二分的这个之后会另外讲实现的$qwq$)
然后继续用二分找到第一个不是0的点,那么中间这一段就都是0
然后判断,如果这一段的0的长度大于可以补的长度了,直接把能补的长度那段赋值成1,然后就补不上了退出
然后如果小于等于,就可以继续补,就把这一段赋值成1继续补重复之间的步骤就成
然后操作1就讲完了,还是比较好理解的呢?
然后是$2\ l\ r$,这个一样是用的二分(听说还有种神仙方法线段树存的是最长0序列长度?这个怎么操作?$mk$下,会学习落实的$qwq$)
差不多套路,首先判断是不是1如果是1让它跳到0去
然后二分查找找出这一段0的长度,然后$ans$取长度$max$就成
最后说下这个二分,就可以结束啦!
首先明确下,$mid$指这一段中连续的0/1(函数中用$k$表示)的长度
然后$query$查找,查这一段的和是多少,如果和=$k\cdot $这段长度,说明这是一段连续长度,说明能继续延伸,就$l=mid+1$
否则不能的话就$r=mid-1$咯
然后注意一下线段树存最长做法和珂朵莉做法还没落实鸭$QAQ$
然后这题我$WA$了半天,一直就是80,90,95的$QAQ$,改到崩溃,一直没想明白为啥$QAQ$
先来贴下提交记录:
在超时边缘疯狂徘徊:)然后我还一直以为是死循环,改了好多遍,然后顺手吸了个氧然后就过来,然后我才知道,我是,人丑常数大,超时了,,,哭了
然后我搞了下把ll全改成int就过去辽
气死:)
我记住ll了我这辈子也不会用ll了x
然后代码在此:
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define rp(i,x,y) for(register ll i=x;i<=y;++i)
#define lc(x) x<<1
#define rc(x) (x<<1)|1
#define md(x,y) (x+y)>>1 const ll N=+;
ll n,m,tr[N<<],add[N<<],trtr[N<<]; inline ll read()
{
char ch=getchar();ll x=;bool y=;
while(ch!='-' && (ch<'' || ch>''))ch=getchar();
if(ch=='-')y=,ch=getchar();
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();
return y?x:-x;
}
inline void pushdown(ll d,ll l,ll r,ll mid)
{
if(add[d]!=)
{
--add[d];
tr[lc(d)]=add[d]*(mid-l+);tr[rc(d)]=add[d]*(r-mid);
add[lc(d)]=add[d]+;add[rc(d)]=add[d]+;
add[d]=;
}
}
void update(ll d,ll l,ll r,ll x,ll y,ll k)
{
if(l>y || x>r)return;
if(l>=x && r<=y){tr[d]=(r-l+)*k;add[d]=k+;return;}
ll mid=md(l,r);pushdown(d,l,r,mid);
if(x<=mid)update(lc(d),l,mid,x,y,k); if(mid<y)update(rc(d),mid+,r,x,y,k);
tr[d]=tr[lc(d)]+tr[rc(d)];
}
void build(ll d,ll l,ll r)
{
if(l==r){tr[d]=;return;}
ll mid=md(l,r);
build(lc(d),l,mid);build(rc(d),mid+,r);
tr[d]=tr[lc(d)]+tr[rc(d)];
}
ll query(ll d,ll l,ll r,ll x,ll y)
{
if(l>y||x>r)return ;if(x<=l&&r<=y)return tr[d];
ll mid=md(l,r),ret=;
pushdown(d,l,r,mid);
if(mid>=x)ret+=query(lc(d),l,mid,x,y); if(mid<y)ret+=query(rc(d),mid+,r,x,y);
return ret;
}
inline ll efcz(ll x,ll y,ll k)
{
if (x>y) return -;
ll l=,r=y-x,mid;
while (l<=r)
{
mid=md(l,r);
if(query(,,n,x,x+mid)==k*(mid+))l=mid+;
else r=mid-;
}
return l;
}
inline void work1(){ll t1=read(),t2=read();update(,,n,t1,t2,);return;}
inline void work2()
{
ll t1=read(),t2=read(),t3=read(),t4=read();
int num=query(,,n,t1,t2),p=;
update(,,n,t1,t2,);
if (num>=t4-t3+-query(,,n,t3,t4))update(,,n,t3,t4,);
else
{
if(num!=)
{
while()
{
if (query(,,n,t3,t3)==){p=efcz(t3,t4,);t3+=p;}
p=efcz(t3,t4,);
if(p==-)break;
if (p>num){update(,,n,t3,t3+num-,);break;}
update(,,n,t3,t3+p-,);num-=p;t3+=p;
}
}
}
}
inline void work3()
{
ll t1=read(),t2=read();
ll ans=,p=;
while()
{
if (query(,,n,t1,t1)==){p=efcz(t1,t2,);t1+=p;}
p=efcz(t1,t2,);
if(p==-)break;
ans=max(ans,p);t1+=p;
if(t1>t2)break;
}
printf("%lld\n",ans);
} int main()
{
n=read();m=read();build(,,n);
while(m--){ll t=read();if(t==)work1();if(t==)work2();if(t==)work3();}
return ;
}
over
昂还有就我认真思考了下发现,分块应该是可以做的?
$umm$然后就尝试用分块写了一发
$vjudge$上过了,然后洛谷上T了
(...什么鬼啊我线段树$vjudge\ T$洛谷过,然后分块$vjudge$过洛谷$T$10个点嘤嘤嘤
嗷然后我吸氧过去了,先这样趴$QAQ$
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rp(i,x,y) for(register int i=x;i<=y;++i)
#define my(i,x,y) for(register int i=x;i>=y;--i) const ll N=+;
int n,m,len,sum,ans,l,r,t,a[N],block[N],siz[N],cnt[N],ml[N],mr[N],bl[N],br[N],b[N],mx[N]; inline int read()
{
char ch=getchar();int x=;bool y=;
while(ch!='-' && (ch<'' || ch>''))ch=getchar();
if(ch=='-')ch=getchar(),y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();
return y?x:-x;
}
inline void move(ll l,ll r){rp(i,l,r){if(sum==)return;if(a[i]==)a[i]=,--sum;}}
inline void clr(ll l,ll r){rp(i,l,r)a[i]=;}
inline void add(ll l,ll r){rp(i,l,r)a[i]=;}
inline void full(ll x){b[x]=;mx[x]=ml[x]=mr[x]=;cnt[x]=siz[x];}
inline void empt(ll x){b[x]=;mx[x]=ml[x]=mr[x]=siz[x];cnt[x]=;}
inline void pushdown(int x)
{
if(b[x]==)clr(bl[x],br[x]);
if(b[x]==)add(bl[x],br[x]);
b[x]=;
}
inline void recount(int x)
{
cnt[x]=;int tmp=;mx[x]=;ml[x]=siz[x];mr[x]=siz[x];
rp(i,bl[x],br[x])
{
if(a[i]==)++tmp;else tmp=;
mx[x]=max(mx[x],tmp);cnt[x]+=a[i];
}
rp(i,bl[x],br[x])if(a[i]==){ml[x]=i-bl[x];break;}
my(i,br[x],bl[x])if(a[i]==){mr[x]=br[x]-i;return;}
}
inline void work1()
{
l=read();r=read();
if(block[r]-block[l]<){pushdown(block[l]);pushdown(block[r]);clr(l,r);recount(block[l]);recount(block[r]);return;}
rp(i,block[l]+,block[r]-){b[i]=;mx[i]=ml[i]=mr[i]=siz[i];cnt[i]=;}
pushdown(block[l]);pushdown(block[r]);
clr(l,br[block[l]]);clr(bl[block[r]],r);
recount(block[l]);recount(block[r]);
}
inline void work2()
{
l=read();r=read();sum=;
if(block[r]-block[l]<)
{
pushdown(block[l]);pushdown(block[r]);
rp(i,l,r)if(a[i]==)++sum;clr(l,r);
recount(block[l]);recount(block[r]);
return;
}
rp(i,block[l]+,block[r]-){sum+=cnt[i];empt(i);}
pushdown(block[l]);pushdown(block[r]);
rp(i,l,br[block[l]])if(a[i]==)++sum;rp(i,bl[block[r]],r)if(a[i]==)++sum;
clr(l,br[block[l]]);clr(bl[block[r]],r);
recount(block[l]);recount(block[r]);
}
inline void work3()
{
l=read();r=read();
if(block[r]-block[l]<)
{
pushdown(block[l]);pushdown(block[r]);
move(l,r);
recount(block[l]);recount(block[r]);
return;
}
pushdown(block[l]);move(l,br[block[l]]);recount(block[l]);if(sum==)return;
rp(i,block[l]+,block[r]-)
{
if(siz[i]-cnt[i]>sum){pushdown(i);move(bl[i],br[i]);recount(i);return;}
else{sum-=(siz[i]-cnt[i]);full(i);}
if(sum==)return;
}
pushdown(block[r]);move(bl[block[r]],r);recount(block[r]);
}
inline void work4()
{
l=read();r=read();
ans=sum=;
if(block[r]-block[l]<)
{
pushdown(block[l]);pushdown(block[r]);
rp(i,l,r){if(a[i]==)++sum;else sum=;ans=max(sum,ans);}
printf("%d\n",ans);
return;
}
pushdown(block[l]);
rp(i,l,br[block[l]]){if(a[i]==)sum++;else sum=;ans=max(sum,ans);}
rp(i,block[l]+,block[r]-)
{
sum=sum+ml[i];ans=max(ans,max(sum,mx[i]));
if(siz[i]!=ml[i])sum=mr[i],ans=max(ans,sum);
}
pushdown(block[r]);rp(i,bl[block[r]],r){if(a[i]==)sum++;else sum=;ans=max(sum,ans);}
printf("%d\n",ans);
} int main()
{
n=read();m=read();
len=sqrt(n);
for(int i=;i<=n;i++)
{
a[i]=;
block[i]=(i-)/len+;++siz[block[i]];++cnt[block[i]];
if(!bl[block[i]])bl[block[i]]=i;br[block[i]]=i;
}
for(int i=;i<=m;i++)
{
t=read();
if(t==){work1();continue;}
if(t==){work2();work3();continue;}
work4();
}
return ;
}