P4344 [SHOI2015]脑洞治疗仪 题解
大家好，我喜欢暴力数据结构，所以我用分块卡过了这道题。
之前题解里面没有分块，这里补充分块做法及优化。
我们规定脑洞是 0，正常是 1。
分块，需要维护的是每个块 0 的前缀长度，0 的后缀长度，最长连续 0 的长度,0 的个数，1 的个数，以及一个 tag 记录是否全部推平。然后初始化函数和推平函数很容易想到了。
下面是代码：
inline void build(int x){
tag[x]=-1;
int l=L[x],r=R[x],s=0;
pre[x]=suf[x]=b[x]=sum[x]=ss[x]=0;
for(register int i=l;i<=r;i++){
if(a[i])
break;
pre[x]++;
}
for(register int i=r;i>=l;i--){
if(a[i])
break;
suf[x]++;
}
for(register int i=l;i<=r;i++){
if(!a[i]){
s++;
sum[x]++;
continue;
}
ss[x]++;
b[x]=max(b[x],s);
s=0;
}
b[x]=max(b[x],s);
return;
}
inline void change(int x){
if(tag[x]==-1)
return;
if(tag[x]==1){
for(register int i=L[x];i<=R[x];i++)
a[i]=1;
tag[x]=-1;
pre[x]=suf[x]=b[x]=sum[x]=0;
ss[x]=R[x]-L[x]+1;
}
if(tag[x]!=-1){
for(register int i=L[x];i<=R[x];i++)
a[i]=0;
tag[x]=-1;
pre[x]=suf[x]=b[x]=sum[x]=R[x]-L[x]+1;
ss[x]=0;
}
return;
}查询就是参照序列操作，直接顺着扫一遍即可，注意要处理块与块连接的地方，如果 0 全部填满这个块，说明可以把两边都连起来。
接着处理区间修改，挖脑洞就是把一部分全部改为 0，直接推平即可。注意要修改 tag。
然后是治疗，分为两部分。第一部分是查询 1，然后将 0；第二部分是把这些数量全部填到
第一部分很简单，直接统计即可，记录 res。第二部分就遍历每个块，如果当前块 0 的个数比 res 大就一个一个填，接着结束，否则就区间直接填入。如果填到最后有剩余就不管。由此得出代码。
写完就会就能获得 50 分的好成绩。
下面说一个大优化，加了能快很多，再加点细枝末节的就能过了。
我们可以看到，build 函数的重构我们在代码中出现的次数太多了，可以针对这个优化。
第一步是把 build 处理一车标记的地方复制到 change 函数里面，然后就可以省去 build 的循环。
第二步是把查询中能解决的重构都干掉，不难看出查询的地方有很多 build，因为没有修改这些都可以替换为 change，把重构全部干掉！
第三步是把区间修改的能不重构就不重构，具体一点是如果之前的 tag 为 0，就不用改了。
第四步是移植脑组织的计数可以和修改放在一起，又可以干掉一些重构。
再加个快读快输就能过了（好像并不能快多少）。
完整代码：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define each(i, x) for (auto& i : (x))
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define dbg(x) (cerr << "(dbg) " << #x " = " << (x) << '\n')
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define up(x, y) (((x) < (y)) && ((x) = (y)))
#define down(x, y) (((x) > (y)) && ((x) = (y)))
#define y1 y1__
namespace FastIO {
const int SZ=(1<<21)+1;
struct I {
char ibuf[SZ],*iS,*iT,c;int f,_eof;FILE*fi;
I(FILE*f):fi(f){}
inline char Gc(){return iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SZ,fi),(iS==iT?EOF:*iS++)):*iS++;}
inline ll operator()(){ll x;operator()(x);return x;}
inline I&operator()(char&x){x=Gc();return*this;}
inline I&operator()(char*s){for(c=Gc();c<32||c>126||c==' ';)c=Gc();for(;c>31&&c<127&&c!=' '&&c!='\n'&&c!='\r';++s,c=Gc())*s=c;*s=0;return*this;}
template<class T>inline I&operator()(T&x){_eof=0;for(f=1,c=Gc();(c<'0'||c>'9')&&!_eof;c=Gc()){if(c=='-')f=-1;_eof|=c==EOF;}for(x=0;c<='9'&&c>='0'&&!_eof;c=Gc())x=x*10+(c&15),_eof|=c==EOF;x*=f;return*this;}
template<class T>I&operator()(T*x,const int&n,const int&st=1){rep(i,st,n){operator()(x[i]);}return*this;}
} in(stdin);
struct O {
char obuf[SZ],*oS=obuf,*oT=oS+SZ-1,qu[55];int f,qr;FILE*fi;
O(FILE*f):fi(f){}
~O(){Flush();}
inline void Flush(){fwrite(obuf,1,oS-obuf,fi),oS=obuf;}
inline O&operator()(char x){*oS++=x;if(oS==oT)Flush();return*this;}
inline O&operator()(const char*s){int len=strlen(s);for(f=0;f<len;++f)operator()(s[f]);return*this;}
template<class T>inline O&operator()(T x){if(!x)operator()('0');if(x<0)operator()('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)operator()(qu[qr--]);return*this;}
template<class T>O&operator()(T*x,const int&n,const char&ed=' ',const int&st=1){rep(i,st,n)operator()(x[i])(ed);return*this;}
} out(stdout);
}
using FastIO::in;using FastIO::out;
const int N=2e5+10;
const int M=500;
int n,m,t,L[M],R[M],pos[N];
int a[N],tag[M],sum[M],ss[M],pre[M],suf[M],b[M];
inline void build(int x){
tag[x]=-1;
int l=L[x],r=R[x],s=0;
pre[x]=suf[x]=b[x]=sum[x]=ss[x]=0;
for(register int i=l;i<=r;i++){
if(a[i])
break;
pre[x]++;
}
for(register int i=r;i>=l;i--){
if(a[i])
break;
suf[x]++;
}
for(register int i=l;i<=r;i++){
if(!a[i]){
s++;
sum[x]++;
continue;
}
ss[x]++;
b[x]=max(b[x],s);
s=0;
}
b[x]=max(b[x],s);
return;
}
inline void change(int x){
if(tag[x]==-1)
return;
if(tag[x]==1){
for(register int i=L[x];i<=R[x];i++)
a[i]=1;
tag[x]=-1;
pre[x]=suf[x]=b[x]=sum[x]=0;
ss[x]=R[x]-L[x]+1;
}
if(tag[x]!=-1){
for(register int i=L[x];i<=R[x];i++)
a[i]=0;
tag[x]=-1;
pre[x]=suf[x]=b[x]=sum[x]=R[x]-L[x]+1;
ss[x]=0;
}
return;
}
inline void debug(){
cout<<endl<<"debug:\n";
for(int i=1;i<=t;i++){
change(i);
build(i);
}
for(int i=1;i<=n;i++)
cout<<a[i]<<' ';
cout<<endl<<"finish\n";
}
inline void update(int l,int r){
int p=pos[l],q=pos[r];
if(p==q){
if(tag[p]==0)
return;
change(p);
for(register int i=l;i<=r;i++)
a[i]=0;
build(p);
return;
}
if(tag[p]!=0){
change(p);
for(register int i=l;i<=R[p];i++)
a[i]=0;
build(p);
}
for(register int i=p+1;i<=q-1;i++){
tag[i]=ss[i]=0;
pre[i]=suf[i]=sum[i]=b[i]=R[i]-L[i]+1;
}
if(tag[q]!=0){
change(q);
for(register int i=L[q];i<=r;i++)
a[i]=0;
build(q);
}
return;
}
inline void modity(int l,int r,int x,int y){
int p=pos[l],q=pos[r],res=0;
if(p==q){
if(tag[p]==-1)
build(p);
else change(p);
for(register int i=l;i<=r;i++)
res+=a[i];
}
else{
if(tag[p]==-1)
build(p);
else change(p);
for(register int i=l;i<=R[p];i++)
res+=a[i];
if(tag[q]==-1)
build(q);
else change(q);
for(register int i=L[q];i<=r;i++)
res+=a[i];
for(register int i=p+1;i<=q-1;i++)
res+=ss[i];
}
update(l,r);
p=pos[x],q=pos[y];
if(p==q){
change(p);
for(register int i=x;i<=y&&res;i++){
if(a[i]==0)
res--;
a[i]=1;
}
build(p);
return;
}
change(p);
for(register int i=x;i<=R[p]&&res;i++){
if(a[i]==0)
res--;
a[i]=1;
}
build(p);
if(!res)
return;
for(register int i=p+1;i<=q-1;i++){
if(sum[i]>res){
change(i);
for(register int j=L[i];j<=R[i]&&res;j++){
if(a[j]==0)
res--;
a[j]=1;
}
build(i);
return;
}
res-=sum[i];
tag[i]=1;
pre[i]=suf[i]=b[i]=sum[i]=0;
ss[i]=R[i]-L[i]+1;
}
if(!res)
return;
change(q);
for(register int i=L[q];i<=y&&res;i++){
if(a[i]==0)
res--;
a[i]=1;
}
build(q);
return;
}
inline void query(int l,int r){
int p=pos[l],q=pos[r];
int s=0,res=0;
if(p==q){
change(p);
for(register int i=l;i<=r;i++){
if(a[i]){
res=max(res,s);
s=0;
continue;
}
s++;
}
res=max(res,s);
out(res)('\n');
return;
}
change(p);
for(register int i=l;i<=R[p];i++){
if(a[i]){
res=max(res,s);
s=0;
continue;
}
s++;
}
res=max(res,s);
for(register int i=p+1;i<=q-1;i++){
res=max(res,b[i]);
if(b[i]==(R[i]-L[i]+1)){
s+=sum[i];
res=max(res,s);
continue;
}
s+=pre[i];
res=max(res,s);
s=suf[i];
}
change(q);
for(register int i=L[q];i<=r;i++){
if(a[i]){
res=max(res,s);
s=0;
continue;
}
s++;
}
res=max(res,s);
out(res)('\n');
return ;
}
int main()
{
in(n)(m);
t=sqrt(n);
for(int i=1;i<=t;i++){
L[i]=(i-1)*t+1;
R[i]=i*t;
}
if(R[t]<n){
t++;
L[t]=R[t-1]+1;
R[t]=n;
}
for(register int i=1;i<=t;i++){
for(register int j=L[i];j<=R[i];j++){
pos[j]=i;
a[j]=1;
}
tag[i]=-1;
pre[i]=suf[i]=b[i]=sum[i]=0;
ss[i]=R[i]-L[i]+1;
}
int opt,l,r,x,y;
while(m--){
//debug();
in(opt)(l)(r);
if(opt==0){
update(l,r);
continue;
}
if(opt==1){
in(x)(y);
modity(l,r,x,y);
continue;
}
if(opt==2)
query(l,r);
}
return 0;
}