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：

---

input	output
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.然后考虑栅栏之间的影响。

任意两个栅栏A，B之间只有三种情况。

1.A，B不构成包含关系：A，B的答案互不影响。

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

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

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

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

Code：

---