P4198 楼房重建 题解

2021年11月24日 阅读数:2
这篇文章主要向大家介绍P4198 楼房重建 题解,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Description

Luogu传送门c++

Solution

不难想到用斜率来计算能看到多少栋楼房,因为哪些楼房能看到哪些不能被看到是固定的,因此不是单调队列优化\(dp\)什么的。git

暴力作法是 \(O(n^2)\) 的,咱们考虑用线段树来维护。优化

线段树里记录两个值,\(len\)\(maxs\)spa

  • \(len\):表示当前区间能看到多少栋楼房。
  • \(maxs\):当前区间最高的楼房的高度。

咱们发现这道题最难的地方就在于如何向上传递信息。code

下面来分析一下,假设咱们要把 \(ls\)\(rs\) 合并到 \(rt\)递归

\(ls\) 能看到的楼房合并以后也能看到。队列

接下来处理 \(rs\),假设 \(ls\) 中最高的楼房高度是 \(mx\)ip

咱们把 \(rs\) 拆成两半,\(s_1\)\(s_2\)get

  • \(s_1\) 的最大高度大于 \(mx\),递归处理 \(s_1\),再加上 \(s_2\) 中能看到的楼房数量。
  • \(s_1\) 的最大高度小于等于 \(mx\),把 \(s_1\) 所有舍弃,递归处理 \(s_2\)

思路比较清晰了,下面放代码。it

Code

#include <bits/stdc++.h>
#define ls rt << 1
#define rs rt << 1 | 1
#define m(x) t[x].maxs
#define l(x) t[x].len

using namespace std;

inline int read(){
    int x = 0;
    char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x;
}

const int N = 1e5 + 10;
int n, m;
double a[N];
struct Seg_tree{
    double maxs;
    int len;
}t[N << 2];

inline void pushup1(int rt){
    t[rt].maxs = max(t[ls].maxs, t[rs].maxs);
}

inline int pushup2(double mx, int l, int r, int rt){
    if(t[rt].maxs <= mx) return 0;
    if(a[l] > mx) return t[rt].len;
    if(l == r) return a[l] > mx;
    int mid = (l + r) >> 1;
    if(t[ls].maxs <= mx) return pushup2(mx, mid + 1, r, rs);
    else return pushup2(mx, l, mid, ls) + t[rt].len - t[ls].len;//
}

inline void update(int x, int y, int l, int r, int rt){
    if(l == r && l == x){
        t[rt].maxs = (double)y / x;
        t[rt].len = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) update(x, y, l, mid, ls);
    else update(x, y, mid + 1, r, rs);
    pushup1(rt);
    t[rt].len = t[ls].len + pushup2(t[ls].maxs, mid + 1, r, rs);
}

int main(){
    n = read(), m = read();
    for(int i = 1; i <= m; ++i){
        int x = read(), y = read();
        a[x] = (double)y / x;
        update(x, y, 1, n, 1);
        printf("%d\n", t[1].len);
    }
    return 0;
}

\[\_EOF\_ \]