问题分析

我们需要维护一个 $n \times m$ 的停车场，支持两种操作：

1. 单点修改：改变某个车位的占用状态
2. 矩形查询：查询指定矩形区域内最大的全空正方形边长

关键约束：$n \times m \leq 4 \times 10^6$，$q \leq 2000$

算法思路

核心思想：线段树 + 单调队列

利用停车场长条形 ($n \geq m$) 的特点，对行建立线段树，在每个节点维护列方向的信息，使用单调队列高效合并信息。

数据结构设计

节点信息

对于线段树的每个节点 $u$，维护三个数组（长度为 $m$）：

• U[u][i]：从第 $i$ 列向上连续的空位数
• D[u][i]：从第 $i$ 列向下连续的空位数
• L[u][i]：以第 $i$ 列为右端点的最大正方形边长

内存映射

使用一维数组模拟二维数组：

#define a(i, j) A[(i - 1) * m + j]
#define U(u, i) G[(u - 1) * m + i]
#define D(u, i) d[(u - 1) * m + i] 
#define L(u, i) H[(u - 1) * m + i]

算法详解

1. 线段树构建

void build(int u, int l, int r) {
    Max = std::max(Max, u);  // 记录最大节点编号
    
    if (l == r) {  // 叶子节点
        for (int i = 1; i <= m; ++i) {
            U(u, i) = a(l, i);  // 单行时向上/向下就是自身
            D(u, i) = a(l, i);
            L(u, i) = a(l, i);  // 最大正方形就是自身是否为空
        }
        siz(u) = 1;  // 节点包含的行数
    } else {
        int mid = (l + r) / 2;
        build(ls(u), l, mid);
        build(rs(u), mid + 1, r);
        pull(u);  // 合并左右子树信息
    }
}

2. 信息合并（核心算法）

void merge(int u, int P, int Q) {
    siz(u) = siz(P) + siz(Q);
    
    // 初始化两个单调队列
    Lpos[0] = 1, Rpos[0] = 0;  // 队列1：维护U[P]
    Lpos[1] = 1, Rpos[1] = 0;  // 队列2：维护D[Q]
    int pos = 1;  // 当前窗口左边界
    
    for (int i = 1; i <= m; ++i) {
        // 基础信息合并
        L(u, i) = std::max(L(P, i), L(Q, i));
        D(u, i) = (D(P, i) == siz(P)) ? (siz(P) + D(Q, i)) : D(P, i);
        U(u, i) = (U(Q, i) == siz(Q)) ? (siz(Q) + U(P, i)) : U(Q, i);
        
        // 维护单调队列1（U[P]）
        while (Lpos[0] <= Rpos[0] && U(P, stk[0][Rpos[0]]) >= U(P, i))
            Rpos[0]--;
        stk[0][++Rpos[0]] = i;
        
        // 维护单调队列2（D[Q]）  
        while (Lpos[1] <= Rpos[1] && D(Q, stk[1][Rpos[1]]) >= D(Q, i))
            Rpos[1]--;
        stk[1][++Rpos[1]] = i;
        
        // 调整窗口，找到最大正方形
        while (pos <= i && 
               U(P, stk[0][Lpos[0]]) + D(Q, stk[1][Lpos[1]]) < i - pos + 1) {
            if (stk[0][Lpos[0]] == pos) Lpos[0]++;
            if (stk[1][Lpos[1]] == pos) Lpos[1]++;
            pos++;
        }
        
        L(u, i) = std::max(L(u, i), i - pos + 1);
    }
}

3. 查询处理

void query(int u, int l, int r, int x, int y) {
    if (x <= l && r <= y) {  // 完全包含
        tot++;
        solve_copy(tot, u);  // 复制节点信息
        return;
    }
    
    int mid = (l + r) / 2;
    if (x <= mid) query(ls(u), l, mid, x, y);
    if (y > mid) query(rs(u), mid + 1, r, x, y);
}

查询时收集所有相关节点，然后线性合并：

tot = Max + 5;
query(1, 1, n, l, r);
int ck = tot + 1;
solve_copy(ck, Max + 6);

// 线性合并所有查询节点
for (int i = Max + 7; i <= tot; ++i) {
    merge(ck + 1, ck, i), ck++;
}

// 在列区间[s,t]中找最大值
int ans = 0;
for (int i = s; i <= t; ++i) {
    ans = std::max(ans, std::min(L(ck, i), i - s + 1));
}

算法原理

单调队列的应用

使用两个单调队列分别维护：

• 向上连续空位的最小值
• 向下连续空位的最小值

通过滑动窗口技术，在 $O(m)$ 时间内找到以每个位置为右端点的最大正方形。

信息合并的正确性

• U[u][i]：如果下层节点完全为空，可以继续向上延伸
• D[u][i]：如果上层节点完全为空，可以继续向下延伸
• L[u][i]：取左右子树的最大值，以及跨越中线的最大值

复杂度分析

• 建树：$O(nm)$
• 单次修改：$O(m \log n)$
• 单次查询：$O(m \log n)$（收集节点）+ $O(km)$（合并节点），其中 $k$ 是查询涉及的节点数

由于 $q \leq 2000$，总复杂度可以接受。

算法优势

1. 利用数据特点：针对 $n \geq m$ 的长条形结构优化
2. 高效合并：使用单调队列实现 $O(m)$ 的节点合并
3. 内存紧凑：一维数组模拟二维，减少内存开销
4. 支持动态：线段树框架天然支持单点修改

总结

本题通过巧妙的线段树设计和单调队列应用，高效解决了带修改的最大空正方形查询问题。算法的核心创新在于：

• 将二维问题转化为一维线段树上的信息维护
• 使用单调队列快速计算跨越中线的最大正方形
• 紧凑的内存布局处理大规模数据

该解法在理论复杂度和工程实现上都达到了很好的平衡，体现了对问题特征的深刻理解和算法设计的精妙技巧。