首先容易观察出这个东西是个半群。操作为 1-side 矩形修改，1-side 矩形查询，且两个方向不同。

如果允许离线，一种常用方法是对下标扫描线，做到 $O(q\log q)$。然而不允许，急。

考虑时间线段树，每个节点维护当前子树内所有半群信息在所有位置的并，容易发现对一段长为 $L$ 的区间，只有 $O(L)$ 个本质不同的半群信息连续段。

采用归并（二进制分组）合并信息，修改的总复杂度为 $O(q\log n)$ 的，或者说均摊 $O(\log n)$。之所以是 $\log n$ 而不是 $\log q$ 是因为对于长度达到 $O(n)$ 的段本质不同信息只有 $O(n)$ 个。

容易发现其实这个就是一颗归并树。

查询时找到相关的节点，在上面二分即可，复杂度 $O(\log n\log q)$。