时间戳

首页 > 技术文章 > [洛谷P4198] 楼房重建

[洛谷P4198] 楼房重建

BCOI 2019-03-03 20:43 原文

洛谷题目链接:楼房重建

题目描述

小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

题解: 这题可以用线段树来做.

首先建树,修改的操作都是模板,因为是单点修改,所以不用\(pushdown\),这里就不多说了,关键是如何写\(push\_up\)函数.

首先我们对每个线段树上的节点需要记录一个\(sum\)表示总共能够看到的楼房数量,还需要记录一个\(mx\)表示该区间内最大的斜率.

首先我们考虑将一个区间分成两部分之后能看到的是哪些部分.我们需要记录一个在递归的时候左边的最大斜率,记为\(lmx\),那么会有这样几种情况:

  1. 左边的节点的\(mx\)小于\(lmx\),左边没有楼房可以被看到,递归右半边.
  2. 左边的节点的\(mx\)大于\(lmx\),那么右边原本能被看到的楼房在加入了左边之后也一定能被看到,递归左半边并加上右半边的答案.

这样操作之后\(pushdown\)所需要的时间从\(O(1)\)变成了\(O(logn)\).

具体实现就是这样的:

int up1(double lmx, int x){
    if(t[x].mx <= lmx) return 0;
    if(k[t[x].l] > lmx) return t[x].sum;
    if(t[x].l == t[x].r) return t[x].mx > lmx;
    if(t[ll(x)].mx <= lmx) return up1(lmx, rr(x));
    return up1(lmx, ll(x))+t[x].sum-t[ll(x)].sum;
}

放一下完整代码:

#include<bits/stdc++.h>
#define ll(x) (x << 1)
#define rr(x) (x << 1 | 1)
using namespace std;
const int N = 1e5+5;

int n, m;
double k[N];

struct SegmentTree{ int l, r, sum; double mx; }t[N*4];

int up1(double lmx, int x){
    if(t[x].mx <= lmx) return 0;
    if(k[t[x].l] > lmx) return t[x].sum;
    if(t[x].l == t[x].r) return t[x].mx > lmx;
    if(t[ll(x)].mx <= lmx) return up1(lmx, rr(x));
    return up1(lmx, ll(x))+t[x].sum-t[ll(x)].sum;
}

void up(int x){
    t[x].mx = max(t[ll(x)].mx, t[rr(x)].mx);
    t[x].sum = t[ll(x)].sum+up1(t[ll(x)].mx, rr(x));
}

void build(int l, int r, int x = 1){
    t[x].l = l, t[x].r = r;
    if(l == r) return; int mid = (l+r>>1);
    build(l, mid, ll(x)), build(mid+1, r, rr(x));
}

void update(int pos, int a, int b, int x = 1){
    if(t[x].l == t[x].r){
        t[x].mx = (double)b*1.0/a, t[x].sum = 1; return;
    }
    int mid = (t[x].l+t[x].r>>1);
    if(pos <= mid) update(pos, a, b, ll(x));
    else update(pos, a, b, rr(x)); up(x);
}

int main(){
    int x, y; cin >> n >> m, build(1, n);
    for(int i = 1; i <= m; i++){
        cin >> x >> y; k[x] = (double)y*1.0/x;
        update(x, x, y);
        cout << t[1].sum << endl;
    }
    return 0;
}

推荐阅读