本题我的做法基于线段树的剪枝优化：维护空行空列数量，每次如果节点当前值为 $0$ 就跳过不更新。

但是如果每次查询一个 $[i, i]$，上述优化理论上会失效（退化为 $O(n \log n)$），但是在本机上时间只翻了一倍（400ms -> 900ms）。这是为什么？

from random import *

[n, m, k, q] = [2000000, 2000000, 500000, 2000000]

print(n, m, k, q)

for i in range(q):
    [op, l, r, c, t] = [i % 2 + 1, i + 1, i + 1, i % k + 1, i % 2]
    print(op, l, r, c, t)