合并修改，再建立静态查询结构¶
Codex（GPT-6）：利用最多20段连续修改的条件，设计二维差分与紧凑静态二维线段树的组合、证明、实现和检验。首选程序为 std.cpp。出题人尝试的二维线段树保留为静态查询组件；不能把其不完整的跨维懒标记直接当作正确的动态方案。
为什么按段处理¶
一个连续修改段内部没有查询，可以交换其中各次加法的顺序，并把它们累积到二维差分数组。对于半开矩形 \([x_1,x_2)\times[y_1,y_2)\) ，在四角分别加 \(v,-v,-v,v\) .越过矩阵下边或右边的角无需保存。
第一次遇到查询时，计算二维前缀和，把累积增量加入当前单元值，再清零差分。重建一次静态矩形最大值结构。此后的连续查询复用该结构，直到下一个修改段。开头若直接查询，需要一次初始建树；末尾若只有修改，无需还原。
紧凑二维线段树¶
一维迭代线段树把长度 \(k\) 的叶子放在 \([k,2k)\) ，无需补齐二次幂。二维数组大小为 \(2n\times2m\) .叶子 \((i+n,j+m)\) 保存单元值；先在每个叶行上向上合并列，再合并行。每个节点保存它所代表的行集合与列集合的笛卡尔积上的最大值。
查询先把行区间分为 \(O(\log(n+1))\) 个节点，再在每个行节点上查询列区间，需要 \(O(\log(m+1))\) .节点编号的叶序可能环绕，但迭代区间算法选出的叶集合仍恰好是不重不漏的目标区间，最大值合并满足结合律。
正确性¶
四角差分的二维前缀和在目标矩形内贡献 \(v\) ，在外部贡献0。线性叠加后，还原所得增量等于这一段所有修改逐个执行的结果。
建树时叶子存真实值，每次合并取两部分最大值，因此所有节点的最大值正确。查询按行和列分割成覆盖目标矩形的互不相交块，取这些块的最大值就是答案。每次查询前若有未处理修改就重建，故始终查询到当前矩阵。
不能直接使用的跨维标记¶
二维懒标记需要同时维护行、列方向的信息，不能只把某个列节点的标记临时借给行孩子。具体反例：全零 \(2\times2\) 矩阵，对第一列全部单元加1两次，再查询第一行两列的最大值，应为2。出题人的动态尝试得到0，因为覆盖第一列的标记没有正确贡献到该跨列查询。这个跨维传播缺陷不影响静态二维树的合并不变量；这里仅对静态树作完整使用。
复杂度与数值范围¶
设修改段数为 \(U\le20\) .每次更新只改四角，总时间为 \(O((U+1)nm+Q\log(n+1)\log(m+1))\) ，空间为 \(O(nm)\) .
任一单元的绝对值至多 \(20000+10^5\cdot20000=2000020000<2^{31}\) ，因此树可以保存32位有符号整数。差分及前缀中间值用64位；主数组约占 \(16nm+8nm=24nm\) 字节。查询初值取最小整数，不能取0。普通逐格修改会在大矩形上退化；四维稀疏表的空间也不适合千万格范围。
验证与性能¶
正式数据各运行五次，并单独测量峰值内存。标准程序最慢中位数 1.796455 秒，峰值 234.07 MiB。按2倍向上取整至0.5秒，参考时限为 4 秒。