P4198 楼房重建

    • 792通过
    • 2K提交
  • 题目提供者 chen_zhe Aya
  • 评测方式 云端评测
  • 标签 块状链表,块状数组,分块 线段树 递归 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小A的楼房外有一大片施工工地,工地上有N栋待建的楼房。每天,这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆,数自己能够看到多少栋房子。

    为了简化问题,我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置,第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示,其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交,那么这栋楼房就被认为是可见的。

    施工队的建造总共进行了M天。初始时,所有楼房都还没有开始建造,它们的高度均为0。在第i天,建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大—修建,也可以比原来小—拆除,甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后,他能看到多少栋楼房?

    输入输出格式

    输入格式:

    第一行两个正整数N,M

    接下来M行,每行两个正整数Xi,Yi

    输出格式:

    M行,第i行一个整数表示第i天过后小A能看到的楼房有多少栋

    输入输出样例

    输入样例#1: 复制
    3 4
    2 4
    3 6
    1 1000000000
    1 1
    输出样例#1: 复制
    1
    1
    1
    2

    说明

    对于所有的数据1<=Xi<=N,1<=Yi<=10^9

    N,M<=100000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。