Skip to content

1012: 买房

题目

题目描述

拔娜娜很有钱,现在要给娜娜买房。

这个世界的房子都建在二维平面上,总共有 $n(n\le 10^5)$栋房子,每栋房子都是线段,第$i$房子是线段$(i, 0)-(i, h_i)$,$h_i$是第$i$栋房子的高度。

娜娜站在原点向$x$正半轴看,如果从原点到某栋楼楼顶的连线不与其他的楼相交(交在之前的楼顶的话也看不到),那么娜娜就看得到这栋楼。

一开始,每栋房子高度都是$0$。每天,都会有某一栋房屋的高度都会被修改。

娜娜很任性,看到的高度大于$0$房子都要买,如果高度为$0$,就看不到。 求对于接下来$m(m\le 100000)$天,如果拔娜娜在这天给娜娜买房子,他需要买多少栋。

输入格式

数据第一行表示数据组数$T(T\le 3)$

每组数据的第一行两个整数$n, m$,意义如题目描述。

之后$m$行,每行两个整数$id, height(id \le n, 1 \le height \le 10^9)$,表示$id$号房子的高度改成了$height$,注意$height \ge 1$,也就是说,改完之后的房子高度肯定不是$0$。

输出格式

输出m个整数,表示对于每一天,拔娜娜需要买房的话会买几栋。

不同组数据之间不需要空行。

样例输入

1 3 4 2 4 3 6 1 1000000000 1 1

样例输出

1 1 1 2

数据范围

  • 对于$20\%$的数据,$n \le 10000$
  • 对于另外$20\%$的数据,数据均为随机生成

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!