Skip to content

1132: 买房

题目

题目描述

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

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

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

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

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

输入格式

数据第一行表示数据组数T(T <= 3)

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

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

输出格式

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

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

样例输入

1
3 4
2 4
3 6
1 1000000000
1 1

样例输出

1
1
1
2

数据范围

  • 对于20%的数据,n <= 10000
  • 对于另外20%的数据,数据均为随机生成

Oops! 本题目还没有解答!

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

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

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