[Code+#3] 寻找车位

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
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]>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]>1;
    if(ql<=mid) query(lss,QL,QR);
    if(mid