[Code+#3] 寻找车位

左手的ㄟ右手 2021-09-29 08:38 184阅读 0赞

## Description ##

给定一个大小为 \\(n\\times m\\) 的 \\(01\\) 矩阵。

要求支持：单点翻转，询问子矩形内部最大正方形。

\\(n\\times m\\leq 4\\cdot 10^6,n\\leq m,q\\leq 2000\\)。

## Sol ##

线段树神题。

我们来一步步解决问题。

首先考虑询问整个矩形，且只有一次询问怎么做。

我们可以 \\(O(n)\\) 的枚举矩形的上边界，再 \\(O(m)\\) 的枚举右边界，再安排一个指针表示矩形的左边界，这样可以发现，随着右边界增大，这个指针是单调不减的。那怎么判断当前枚举的正方形是否合法呢？根据这个单调不减的性质，我们可以用一个单调队列来维护这个左指针，具体就不细说了，大概就是每个点记录一个向下最长的一段 \\(1\\) 能够延伸多长就好了。

然后回到该问题。

观察到 \\(q,m\\) 比较小，所以可以让复杂度偏向 \\(q,m\\)。

对 \\(n\\) 这一维开一棵线段树，线段树上每个节点表示的矩形高度都为 \\(m\\)。

然后问题就是如何合并信息，即知道两个子区间的信息能否合并出大区间中跨越 \\(mid\\) 的最大子矩形。

所以我们除了在每个节点维护最大子矩形之外，还要维护两个信息 \\(lmx\[i\],rmx\[i\]\\) 表示第 \\(i\\) 行从左端点和右端点分别最长能延伸多长的一段 \\(1\\)。

然后就支持合并了，具体就是，枚举一个子矩形的下边界 \\(i\\)，然后用两个单调队列维护左儿子的右边界和右儿子的左边界，再拿个指针维护子矩形的上边界，就可以均摊 \\(O(m)\\) 求出以每行为下边界跨越 \\(mid\\) 的最大子矩形了。

不想说了不想说了。

看代码吧。

## Code ##

#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef double db; typedef long long ll; const int N=4e6+5; #define ls x<<1 #define rs x<<1|1 #define lss ls,l,mid,ql,qr #define rss rs,mid+1,r,ql,qr int q1[N],q2[N]; int n,m,q,ret,len; int hd1,tail1,hd2,tail2; struct Node{ int f[N<<2]; int* operator[](int x){return f+x*m;}//这个重载中括号很巧很巧 }mp,lmx,rmx,sum; void pushup(int x,int l,int r){ int mid=l+r>>1,len1=mid-l+1,len2=r-mid; //[l,mid] [mid+1,r] hd1=hd2=1;tail1=tail2=0; for(int j=1,i=1;i<=m;i++){ while(hd1<=tail1 and rmx[ls][q1[tail1]]>=rmx[ls][i]) tail1--; q1[++tail1]=i; while(hd2<=tail2 and lmx[rs][q2[tail2]]>=lmx[rs][i]) tail2--; q2[++tail2]=i; while(hd1<=tail1 and hd2<=tail2 and i-j+1>rmx[ls][q1[hd1]]+lmx[rs][q2[hd2]]){ j++; if(q1[hd1]<j) hd1++; if(q2[hd2]<j) hd2++; } sum[x][i]=max(sum[ls][i],sum[rs][i]); if(hd1<=tail1 and hd2<=tail2) sum[x][i]=max(sum[x][i],i-j+1); } for(int i=1;i<=m;i++) lmx[x][i]=lmx[ls][i]+(lmx[ls][i]==len1?lmx[rs][i]:0), rmx[x][i]=rmx[rs][i]+(rmx[rs][i]==len2?rmx[ls][i]:0); } void build(int x,int l,int r){ if(l==r){ for(int i=1;i<=m;i++) lmx[x][i]=rmx[x][i]=sum[x][i]=mp[l][i]; return; } int mid=l+r>>1; build(ls,l,mid),build(rs,mid+1,r); pushup(x,l,r); } void modify(int x,int l,int r,int ql,int qr,int c){ if(l==r){ lmx[x][c]^=1;rmx[x][c]=sum[x][c]=lmx[x][c]; return; } int mid=l+r>>1; ql<=mid?modify(lss,c):modify(rss,c); pushup(x,l,r); } void merge(int x,int l,int r,int QL,int QR){ hd1=hd2=1;tail1=tail2=0; int len1=len,len2=r-l+1; for(int j=QL,i=QL;i<=QR;i++){ while(hd1<=tail1 and rmx[0][q1[tail1]]>=rmx[0][i]) tail1--; q1[++tail1]=i; while(hd2<=tail2 and lmx[x][q2[tail2]]>=lmx[x][i]) tail2--; q2[++tail2]=i; while(hd1<=tail1 and hd2<=tail2 and i-j+1>rmx[0][q1[hd1]]+lmx[x][q2[hd2]]){ j++; if(q1[hd1]<j) hd1++; if(q2[hd2]<j) hd2++; } if(hd1<=tail1 and hd2<=tail2) ret=max(ret,i-j+1); } for(int i=QL;i<=QR;i++) lmx[0][i]=lmx[0][i]+(lmx[0][i]==len1?lmx[x][i]:0), rmx[0][i]=rmx[x][i]+(rmx[x][i]==len2?rmx[0][i]:0); } void query(int x,int l,int r,int ql,int qr,int QL,int QR){ if(ql<=l and r<=qr){ for(int i=QL;i<=QR;i++) ret=max(ret,min(sum[x][i],i-QL+1)); merge(x,l,r,QL,QR); len+=r-l+1; return; } int mid=l+r>>1; if(ql<=mid) query(lss,QL,QR); if(mid<qr) query(rss,QL,QR); } int query(int ql,int qr,int QL,int QR){ ret=len=0; for(int i=1;i<=m;i++) lmx[0][i]=rmx[0][i]=0; query(1,1,n,ql,qr,QL,QR); return ret; } signed 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]); build(1,1,n); while(q--){ int opt; scanf("%d",&opt); if(!opt){ int x,y; scanf("%d%d",&x,&y); modify(1,1,n,x,x,y); } else{ int l,s,r,t; scanf("%d%d%d%d",&l,&s,&r,&t); printf("%d\n",query(l,r,s,t)); } } return 0; }

转载于:https://www.cnblogs.com/YoungNeal/p/10392316.html