ROI 2015 Day1 珍珠刺绣

· · 题解

因为原先的图是一棵树，显然每次询问的子图都是森林。

森林连通块数量启发我们使用 V - E 计算。

把边分成横向的和纵向的两部分，然后我们需要维护：一个子矩形内点数量，横向边数量，纵向边数量。

边数量显然是可以把每个边的贡献算到其中一个端点上进行维护的，这里不妨将 (x, y) 和 (x, y + 1) 的边的贡献放到 (x, y) 上，(x, y) 和 (x + 1, y) 的边同理贡献放到 (x, y) 上，则横向边数量为 (x_1 , y_1 ) 到 (x_2 , y_2 − 1) 的贡献和，纵向边同理，数量为 (x_1 , y_1 ) 到 (x_2 − 1, y_2 ) 的贡献和。

注意到点数和边数是 O(n) 的，因此可以离线之后用扫描线和树状数组维护。

感觉思路上和 APIO2017 斑斓之地 类似。

Submission