四个方向是本质相同的，不妨考虑算右上方合法的点数。对于询问 $(x_1,y_1)$，一个点 $(x_2,y_2)\pod{x_2\ge x_1,y_2\ge y_1}$ 合法当且仅当 $y_2\le \min\{b_i\mid x_1\le a_i\le x_2,b_i\ge y_1\}$。

按照 $y$ 从大到小处理，只需要执行单点修改和查一段后缀的每个前缀最小值的和，这可以用线段树维护（经典 NOIP 题）。时间复杂度 $O(n+m+K\log^2(n+m)+q\log(n+m))$。