省流：利用等价类分治 + 线性 RMQ。

对列建线段树，把修改、查询的列区间分别挂到规范节点。节点 $u$ 的行等价类由挂在其整棵子树中的事件的 $x_1,x_2+1$ 划分。因此父节点的划分比儿子细。记：

• $U_u(C)$：挂在 $u$ 的修改在行类 $C$ 上增加的值；
• $F_u(C)$：只考虑 $u$ 子树内的修改，行类 $C$ 在 $u$ 所辖列中的最大值；
• $H_u(C)$：行类 $C$ 中，各行受到严格祖先修改后的值的最大值。

这三项满足 $F_u(C)=U_u(C)+\max(F_{\mathrm L}(C),F_{\mathrm R}(C))$， 叶子处为 $F_u(C)=U_u(C)$。从根往下，根的 $H$ 全为 $0$；对儿子的一个粗行类 $D$，有 $H_{\mathrm{child}}(D)=\max_{C\subseteq D}\bigl(H_u(C)+U_u(C)\bigr)$。 于是挂在 $u$ 的查询，其该列节点的贡献就是查询行范围内各类 $H_u(C)+F_u(C)$ 的最大值。每个查询把所有所挂节点的贡献再取一次最大值即可。

少掉的一只 $\log$ 在两处：

• 1. 按行坐标统一排序所有事件端点，再沿事件的列区间走线段树，将端点追加到所经过节点。一次列区间遍历只访问 $O(\log n)$ 个节点，所以全部等价类总数是 $O((m+q)\log n)$；各节点端点已经有序，不必逐节点排序或二分定位。
• 1. $U_u$ 是区间加，把挂在 $u$ 的修改在行端点处记为 $+v,-v$，扫描该节点的等价类即可线性求出全部 $U_u(C)$。前一道半环乘法题不能这样做，因为它禁止求逆，所以局部区间乘仍需一只 $\log$。

自底向上的 $F$ 和自顶向下的 $H$ 都用双指针在父子的有序行类间转换，总量为 $O((m+q)\log n)$。 节点内对 $H_u+F_u$ 建线性预处理、$O(1)$ 查询的静态 RMQ，例如笛卡尔树配线性 LCA；所有查询挂载次数也是 $O(q\log n)$。全局端点排序的 $O((m+q)\log(m+q))$ 在本题范围下同属一只 $\log$。 所以严格得到 $O((n+m+q)\log n)$ 时间、$O((n+m+q)\log n)$ 空间。若节点内改用普通最大值线段树查询，就会在查询上重新多出一只 $\log$。