[BZOJ29957] 楼房重建 - 线段树

时间：2021-10-24 23:24:25

2957: 楼房重建

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 3294  Solved: 1554
[Submit][Status][Discuss]

Description

　　小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
　　为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
　　施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大---修建，也可以比原来小---拆除，甚至可以保持不变---建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？

Input

　　第一行两个正整数N,M
　　接下来M行，每行两个正整数Xi,Yi

Output

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

Sample Input

3 4
2 4
3 6
1 1000000000
1 1

Sample Output

1
1
1
2
数据约定
　　对于所有的数据1<=Xi<=N，1<=Yi<=10^9
N,M<=100000
题解：
那线段树维护区间的最大斜率和斜率最长上升子序列的长度；
甚至建树都不需要；
唯一的问题就是update，我们好像不可以O(1)合并。
我们把一个序列分为左右两端记为L, R；
如果R的最大斜率小于L的最大斜率，那么有区间直接就不用考虑了；
如果R的最大斜率大于L的最大斜率，那么我们二分R区间，像这样递归下去；
Code：
#include <iostream>

#include <cstdio>

using namespace std;

struct segment

{

    int len;

    long double mx;

}t[];

#define ls(o) o<<1

#define rs(o) o<<1|1

#define mx(o) t[o].mx

#define len(o) t[o].len

inline int count(int l, int r, int o, long double hi)

{

    if (l == r) return mx(o) > hi;

    int mid = l + r >> ;

    if (mx(ls(o)) <= hi) return count(mid + , r, rs(o), hi);

    return len(o) - len(ls(o)) + count(l, mid, ls(o), hi);

}

inline void change(int l, int r, int o, int to, long double k)

{

    if (l == r)

    {

        len(o) = ;

        mx(o) = k;

        return ;

    }

    int mid = l + r >> ;

    if (to <= mid) change(l, mid, ls(o), to, k);

    else change(mid + , r, rs(o), to, k);

    mx(o) = max(mx(ls(o)), mx(rs(o)));

    len(o) = len(ls(o)) + count(mid + , r, rs(o), mx(ls(o)));

}

int main()

{

    int n, m;

    scanf("%d%d", &n, &m);

    while (m--)

    {

        int x, y;

        scanf("%d%d", &x, &y);

        change(, n, , x, (long double)y / x);

        printf("%d\n", len());

    }

    return ;

}

相关文章