D
有一个 \(h \times w\) 的网格图，有 \(n\) 个点 \((a_i, b_i)\) 以及 \(n - 1\) 条边，每条边形如 \(op \ x \ y\)，表示位于 \((x, y)\) 的点与位于 \((x, y + 1) / (x + 1, y)\) 的点之间有连边（给的位置上一定有点，\(n\) 个点是连通的）。
现在有 \(T\) 组询问，每组询问给一个矩形，覆盖 \(x1 \le x \le x2 \ \& \& \ y1 \le y \le y2\) 的所有 \((x, y)\)，问只考虑完全包含在这个矩形内的点和边一共有多少个连通块。
\(1 \le h, w, n, T \le 1.5 \times 10^5\)。
这个题首先由抓住只有 \(n - 1\) 条边且 \(n\) 个点连通这件事，意味着这 \(n\) 个点组成了一棵树。所以问由多少个连通块其实就是”点数 \(-\) 边数“。
点数好求，搞个扫描线可以求出来，主要是边数。我们以 \((x, y)\) 与 \((x, y + 1)\) 之间的这种水平边为例，这种边被完全包含当且仅当 \(x1 \le x \le x2, y1 \le y \le y2 - 1\)，其实也是一个二维数点的形式的形式。但是要把两种边分开做可能有些麻烦，加上点的要做 \(3\) 次扫描线。可以用 \(x1 \le x \le x2, y1 \le y \le y2\) 的减去 \(x1 \le x \le x2, y = y2\) 的这样就可以把前面的丢到一起做，后面的搞个 vector 存起来二分一下即可。
时间复杂度：\(O(n \log n)\)。（都是同级的。）
纯无脑扫描线题，没啥意思。