@[听取MLE声一片](/user/253738) 写分块题解的教皇有空帮蒟蒻看一下吗
by Balor @ 2023-06-10 17:46:06
@[Balor](/user/1010254) 你是写错了球调还是什么？
by 听取MLE声一片 @ 2023-06-10 17:53:25
看看我的题解。
>遍历每个块，如果当前块 0 的个数比 res 大就一个一个填，接着结束，否则就区间直接填入。
by 听取MLE声一片 @ 2023-06-10 17:53:59
@[听取MLE声一片](/user/253738) 是想求调，也想问一下这个询问的正确性
by Balor @ 2023-06-10 17:54:23
@[听取MLE声一片](/user/253738) 思路除了询问和您的题解差不离
by Balor @ 2023-06-10 17:55:24
@[Balor](/user/1010254) 马蜂差距很大实现也有差异我也不好看啊。
你可以去查查块重构之类的问题
by 听取MLE声一片 @ 2023-06-10 18:05:31
@[听取MLE声一片](/user/253738) 呃呃，我发现问题所在了……
最后 更新 $Y$ 的时候没有考虑到 $w_Y$，但是还是 WA 了一些
by Balor @ 2023-06-10 18:05:43
写错了一堆东西。。。放一下调完后开O2能过的代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10,M=1e3+10;
int n,m,st[M],ed[M],one[M],l[M],r[M],cs[M],bar[N],tag[M],Len,cnt;
bool a[N];
int len(int k){return ed[k]-st[k]+1;}
void pushdown(int k){
if(tag[k]==-1)return;
for(int i=st[k];i<=ed[k];i++)a[i]=tag[k];
tag[k]=-1;return;
}
void pushup(int k){
int now=0;l[k]=-1;r[k]=-1;one[k]=cs[k]=0;
for(int i=st[k];i<=ed[k];i++)if(a[i])l[k]=i-st[k],i=ed[k]+1;
for(int i=ed[k];i>=st[k];i--)if(a[i])r[k]=ed[k]-i,i=st[k]-1;
for(int i=st[k];i<=ed[k];i++)if(a[i])cs[k]=max(cs[k],now),now=0;else now++;
cs[k]=max(cs[k],now);
if(l[k]<0)l[k]=len(k);if(r[k]<0)r[k]=len(k);
for(int i=st[k];i<=ed[k];i++)one[k]+=a[i];
return;
}
void init(){
Len=sqrt(n);cnt=n/Len+bool(n%Len);
for(int i=1;i<=cnt;i++){
st[i]=ed[i-1]+1;ed[i]=i*Len;
for(int j=st[i];j<=ed[i];j++)bar[j]=i,a[j]=1;
tag[i]=-1;one[i]=len(i);
}one[cnt]-=ed[cnt]-n;ed[cnt]=n;
return;
}
void debug(){
for(int i=1;i<=cnt;i++)pushdown(i),pushup(i);
for(int i=1;i<=cnt;i++){
for(int j=st[i];j<ed[i];j++)printf("%d ",a[j]);
printf("%d|",a[ed[i]]);
}puts("");
for(int i=1;i<=cnt;i++)printf("%d %d %d %d %d|",l[i],r[i],cs[i],one[i],tag[i]);
puts("\n-----");
return;
}
int modify(int x,int y){
int X=bar[x],Y=bar[y],ret=0;
if(X==Y){
pushdown(X);
for(int i=x;i<=y;i++)ret+=a[i];
for(int i=x;i<=y;i++)a[i]=0;
pushup(X);return ret;
}
for(int i=X+1;i<=Y-1;i++)ret+=one[i],tag[i]=one[i]=0,l[i]=r[i]=cs[i]=len(i);
pushdown(X);for(int i=x;i<=ed[X];i++)ret+=a[i],a[i]=0;pushup(X);
pushdown(Y);for(int i=st[Y];i<=y;i++)ret+=a[i],a[i]=0;pushup(Y);
// debug();
return ret;
}
void update(int x,int y,int val){
int X=bar[x],Y=bar[y];
if(X==Y){
pushdown(X);
for(int i=x;i<=y&&val;i++)if(!a[i])a[i]=val--;
pushup(X);return;
}
pushdown(X);
for(int i=x;i<=ed[X]&&val;i++)if(!a[i])a[i]=val--;
pushup(X);
if(!val)return;
for(int i=X+1;i<=Y-1&&val;i++){
if(val<len(i)-one[i]){
pushdown(i);
for(int j=st[i];j<=ed[i]&&val;j++)if(!a[j])a[j]=val--;
pushup(i);
return;
}
val-=len(i)-one[i];
tag[i]=1;one[i]=len(i);l[i]=r[i]=cs[i]=0;
}
if(!val)return;
pushdown(Y);
for(int i=st[Y];i<=y&&val;i++)if(!a[i])a[i]=val--;
pushup(Y);
// debug();
return;
}
int query(int x,int y){
int X=bar[x],Y=bar[y],ret=0,now=0;
if(X==Y){
pushdown(X);pushup(X);
for(int i=x;i<=y;i++)if(a[i])ret=max(ret,now),now=0;else now++;
return max(ret,now);
}
pushdown(X);pushup(X);
for(int i=x;i<=ed[X];i++)if(a[i])ret=max(ret,now),now=0;else now++;ret=max(ret,now);
for(int i=X+1;i<=Y-1;i++){
ret=max(ret,cs[i]);
if(!one[i])now+=len(i),ret=max(ret,now);
else now+=l[i],ret=max(ret,now),now=r[i];
}
pushdown(Y);pushup(Y);
for(int i=st[Y];i<=y;i++)if(a[i])ret=max(ret,now),now=0;else now++;ret=max(ret,now);
return ret;
}
signed main(){
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=m;i++){
int opt,L,R,L_=0,R_=0;
scanf("%d%d%d",&opt,&L,&R);
if(opt==0)modify(L,R);
else if(opt==1)scanf("%d%d",&L_,&R_),opt=modify(L,R),update(L_,R_,opt);
else if(opt==2)printf("%d\n",query(L,R));
}
system("pause");
return 0;
}
```
~~大帝写的代码甚至要优化，我是不是小常数体质啊~~
by Balor @ 2023-06-13 17:21:49