题解 P4259 【[Code+#3]寻找车位】

线段树神题……这年头好像什么东西都可以放到线段树上去跑一跑…… ___________________ ## 本题题解 首先题目的操作次数十分的小,q只有2000意味着我们只是需要把复杂度控制在诸如$O(qmlogn)$的复杂度即可通过本题 那么我们发现事实上对于静态的问题来讲我们的时间复杂度下限是$O(nm)$的，因为我们至少需要把整个矩阵扫一遍才能了解最大正方形的位置 那么动态的问题显然不能做的比静态的问题更好，因此我们肯定是先做一个预处理然后使得每次修改的时候修改的部分尽可能的小而已，那么我们会发现线段树是一个十分优秀的工具，线段树的存在使得我们可以在单点修改的时候不会修改过多的节点，而且还支持我们的区间查询。 那么我们要做的就是先去想一个静态的暴力解法，然后把这个暴力解法搬到线段树上，去做一个快速的暴力，然后我们就可以通过这道题了 ____________________ ### 暴力:单调队列 让我们来想一个平凡的暴力 我们首先$O(n)$的枚举最大正方形的上边界，然后我们$O(m)$的枚举最大正方形右端点，现在我们需要找到最优的左端点，可以发现随着右端点的增加，左端点的位置是单调不减的，接下来我们处理出一个数组表示这个点向下有多少个连续的1，那么左右端点间的区间最小值就是这个正方形最大可能的边长，那么我们就可以使用单调队列维护区间最小值，之后我们对于一个右端点判定一下区间最小值是否小于当前的左右端点之间的长度，如果小于了就把左端点向左挪一格然后继续判断，然后更新一下答案即可(相信来看这篇题解的人应该都知道这个东西怎么做) 那么我们现在要把这个东西挪到线段树上来…… 该怎么处理呢？我们仅仅对于n这一维开一个线段树，因此线段树上每一个节点所表示的矩形高度均为m 我们发现因为复杂度仅仅要求$O(mlogn)$因此我们还是可以使用一些暴力的 比如说枚举上边界这个暴力是可以保留下来的 那么我们现在在这个线段树上去枚举上边界，接下来我们要对每个上边界i求出一个类似于区间最大值一样的东西，留给我们的就只剩下$O(logn)$的复杂度了 因此一定是使用线段树将这个询问的子矩形在n这一维剖分成$O(logn)$个子矩形，然后$O(1)$的求出每个子矩形内部的最大全1正方形，之后再考虑跨越几个子矩形之间的最大全1正方形了 那么为了$O(1)$的提取信息我们只可能再线段树上处理出一个$val$数组，$val_{i}$表示上边界为i时这个节点所表示的子矩形中的最大全1正方形边长，这样的话$O(nm)$的空间复杂度我们是可以接受的 那么我们现在考虑如何在线段树上维护这个信息，换句话说其他都是线段树的板子，我们唯一在意的就是这个merge函数怎么写 那么我们发现对于$val_{i}$来讲，它显然可以通过取两个孩子的$val_{i}$的max来得到，但是这样的话我们忽略了一种非常重要的情况，就是如何算出跨越两个区间的正方形的边长。 显然我们要求的复杂度是对于每一个$val_{i}$我们可以实现$O(1)$的merge，但是这个东西显然是不现实的，因此我们考虑一下均摊的算法，换句话说我们使用均摊$O(1)$的算法，一口气从1到mmerge完所有的$val_{i}$ 那么我们现在如果从1到m枚举i的话，我们只需要对于每一个上边界i，求出来一个最优的下边界j就可以了，事实上着对应着我们静态暴力时扫一边右端点，对于每个右端点求出一个最优的左端点的过程 和我们的静态暴力一样，这里我们发现当上边界i增长的时候最优下边界j单调不减，因此我们还是可以使用一个单调队列去维护区间最小值，问题来了维护谁的区间最小值？ 这里我们发现这个东西一定跨越了两个子节点的边界线，因此我们可以对每个线段树节点维护两个数组$lf$和$rt$表示i这一行和左边界相邻的全1序列的长度，以及和右边界相邻的全1序列的长度 那么我们现在就只需要分别用两个单调队列维护左儿子的rt数组区间最小值，右儿子的lf数组区间最小值即可了，我们判断这个下边界j的方式合不合法的方法就是判断上下两个边界间的距离是否大于了lf和rt数组区间最小值的和 这样我们就对每一个上边界i以均摊$O(1)$的代价求出了跨越两个孩子的最大的全1正方形，和在两个孩子内部的$val$值取一下max就可以求出$val_{i}$的值了 然后此时我们可能还需要merge下两个孩子的lf和rt数组，那么我们每个节点额外开一个len表示这个节点所代表的子矩形的宽度，那么我们求lf的时候判下左儿子的lf是否是满的，以决定右儿子是否可以接上去，同理rt数组也可以类似的求出了 好了那么我们愉快的merge了两个孩子，现在我们其实已经可以处理单点修改了，我们直接暴力的单点改然后一路merge上去即可 问题来了子矩形询问呢？ 、 首先我们发现跨越了若干个子矩形的答案非常好求，我们以0号节点为1个中间节点，然后按照线段树拆分的顺序从左到右一路merge过去，注意merge的时候原来是从1到m的枚举上边界，现在是从子矩形的上边界到下边界枚举上边界了 现在还剩下最后一个问题，对于线段树上拆分出的$O(logn)$个节点，我们如何提取出它们的答案？ 答案还是枚举上边界，注意到对于一个钦定的上边界i，最大正方形的长度不得超过这个上边界到询问子矩形下边界的距离，因此只需要把$val_{i}$和距离取个min最后把所有上边界的答案取个max就行了，这样我们就可以$O(m)$的提取出每个点的答案了 其实代码还是超级好写的，如果你的线段树板子函数分的好的话，你甚至只需要改一个merge函数就行了 然后这里可能需要我们使用1维数组去动态的模拟二维数组，有一个小trick是可以重载一个'\[]'运算符从而可以直接按照二维数组写就行了 上代码~ ```C // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> using namespace std;const int N=4*1e6+10; int n;int m;int q; struct mar {int f[4*N];inline int* operator [](int x){return f+x*m;}}mp;//重载运算符方便写代码 struct linetree { mar v;mar lf;mar rt;int len[4*N];int ql[N];int qr[N]; int hd1;int tl1;int hd2;int tl2; inline void merge(int p,int p1,int p2)//双指针扫一遍处理节点合并的信息 { hd1=hd2=1;tl1=tl2=0; for(int i=1,j=1;i<=m;i++) { while(hd1<=tl1&&lf[p2][ql[tl1]]>lf[p2][i])tl1--;ql[++tl1]=i;//单调队列插入 while(hd2<=tl2&&rt[p1][qr[tl2]]>rt[p1][i])tl2--;qr[++tl2]=i; while(hd1<=tl1&&hd2<=tl2&&lf[p2][ql[hd1]]+rt[p1][qr[hd2]]<(i-j+1)) {if(ql[hd1]<=j){hd1++;}if(qr[hd2]<=j){hd2++;}j++;} v[p][i]=max(v[p1][i],v[p2][i]);v[p][i]=max(v[p][i],(i-j+1));//左边,右边,中间 } for(int i=1;i<=m;i++)lf[p][i]=(lf[p1][i]==len[p1])?lf[p1][i]+lf[p2][i]:lf[p1][i];//合并lf for(int i=1;i<=m;i++)rt[p][i]=(rt[p2][i]==len[p2])?rt[p2][i]+rt[p1][i]:rt[p2][i];//合并rt } inline int merge(int p1,int p2,int l,int r)//求两个节点的交,询问时使用 { hd1=hd2=1;tl1=tl2=0;int ret=0; for(int i=l,j=l;i<=r;i++) { while(hd1<=tl1&&lf[p2][ql[tl1]]>lf[p2][i])tl1--;ql[++tl1]=i; while(hd2<=tl2&&rt[p1][qr[tl2]]>rt[p1][i])tl2--;qr[++tl2]=i; while(hd1<=tl1&&hd2<=tl2&&lf[p2][ql[hd1]]+rt[p1][qr[hd2]]<(i-j+1)) {if(ql[hd1]==j){hd1++;}if(qr[hd2]==j){hd2++;}j++;} ret=max(ret,(i-j+1)); } for(int i=l;i<=r;i++)lf[p1][i]=(lf[p1][i]==len[p1])?lf[p1][i]+lf[p2][i]:lf[p1][i]; for(int i=l;i<=r;i++)rt[p1][i]=(rt[p2][i]==len[p2])?rt[p2][i]+rt[p1][i]:rt[p2][i]; len[p1]+=len[p2];return ret; } inline void modify(int p,int l,int r,int pos,int px)//修改的话一路merge上去就好了 { if(r-l==1){v[p][px]=lf[p][px]=rt[p][px]=mp[r][px];return;} int mid=(l+r)/2; if(pos<=mid){modify(p<<1,l,mid,pos,px);} else {modify(p<<1|1,mid,r,pos,px);} merge(p,p<<1,p<<1|1); } inline int query(int p,int l,int r,int dl,int dr,int xl,int xr)//询问的话直接一路merge过去即可 { if(dl==l&&dr==r) { int ret=merge(0,p,xl,xr);//提取信息 for(int i=xl;i<=xr;i++)ret=max(ret,min(v[p][i],i-xl+1));return ret;//求交 }int ret=0;int mid=(l+r)/2; if(dl<mid)ret=max(ret,query(p<<1,l,mid,dl,min(dr,mid),xl,xr)); if(mid<dr)ret=max(ret,query(p<<1|1,mid,r,max(dl,mid),dr,xl,xr)); return ret; } inline int cquery(int dl,int dr,int xl,int xr)//记得清空中间节点 { for(int i=1;i<=m;i++)v[0][i]=lf[0][i]=rt[0][i]=0;len[0]=0; return query(1,0,n,dl,dr,xl,xr); } inline void build(int p,int l,int r)//建树的时候也是直接merge就好了 { if(r-l==1){for(int i=1;i<=m;i++)lf[p][i]=rt[p][i]=v[p][i]=mp[r][i];len[p]=1;return;} int mid=(l+r)/2;build(p<<1,l,mid);build(p<<1|1,mid,r);len[p]=len[p<<1]+len[p<<1|1]; merge(p,p<<1,p<<1|1); } }lt; int main() { scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&mp[i][j]);lt.build(1,0,n); for(int i=1,t;i<=q;i++) { scanf("%d",&t); if(t==0){int x;int y;scanf("%d%d",&x,&y);mp[x][y]^=1;lt.modify(1,0,n,x,y);} else { int dl;int dr;int xl;int xr;scanf("%d%d%d%d",&dl,&xl,&dr,&xr); printf("%d\n",lt.cquery(dl-1,dr,xl,xr)); } }return 0;//拜拜程序~ } ```