【CERC2017】Buffalo Barricades

Description:


在一个网格平面上,有\(n\)个点(牛),其中第\(i\)个点在以\((x_i,y_i)\)为右上角的网格中。有\(m\)次操作,每次给出一个点\((x,y)\)(栅栏),表示从\((x,y)\)开始,向左和向下画线直到与之前画的线或坐标轴相交。这样会划分出以\((x,y)\)为右上角的新区域。你需要对每次操作求出,新区域中点的数量。

\(n,m\leq 3 \times 10^5, 1 \leq x_i,y_i \leq 10^9\)

Example:


inputoutput
7
1 1
4 2
6 2
5 3
2 5
4 7
7 5
4
4 4
8 2
9 6
6 5
2
1
3
2

Solution:


1.首先用扫描线+set处理出最终状态下的每个栅栏控制的点的数量。

即求每个牛被哪个栅栏控制。

将所有点(牛和栅栏)按\(y\)坐标递减排序后依次处理每个点。

用set维护当前状态下,所有点组成的栅栏向下延伸将\(x\)坐标分成了几个部分。要处理其中有些栅栏向下延伸的边会被\(y\)坐标比它小但出现时间比他早的栅栏向左延伸的边切掉。

考虑加入一个栅栏点。则模拟向左延伸并删除之前出现(\(y\)坐标比它大)\(x\)坐标比他小,出现时间比他晚的栅栏。直到遇到第一个出现比它早的栅栏,此时该栅栏向左延伸的边被阻断。

考虑统计每个点(牛)最终属于哪个栅栏。当处理到一个点(牛)时,此时\(x\)坐标被之前出现的栅栏分割成了几个部分,显然,该点最终会属于第一个比它的\(x\)坐标大的竖线所代表的栅栏。

2.然后考虑栅栏之间的影响。

任意两个栅栏AB之间只有三种情况。

1.AB不构成包含关系:AB的答案互不影响。

2.A包含B,但A出现的时间比B晚:B的答案不需要被算入A的答案。

3.A包含B,且A出现的时间比B早:B的答案需要被算入A的答案。

因此,只需处理出包含关系构成的森林(每个栅栏向与它最靠近的在它右上的栅栏连边,该过程可以在维护set的时候顺便完成),然后按照时间顺序依次处理每个栅栏,每个栅栏的最终答案就是当前子树的size,然后将它的父边删去。

然而这么搞不好写(lct滚呐),可以按时间倒序处理,(考虑先每个点孤立,不停加边)用并查集维护答案。

Code: