P4198 楼房重建 题解

Description

Luogu传送门

Solution

不难想到用斜率来计算能看到多少栋楼房，由于哪些楼房能看到哪些不能被看到是固定的，所以不是单调队列优化(dp)什么的。

暴力做法是 (O(n^2)) 的，我们考虑用线段树来维护。

线段树里记录两个值，(len) 和 (maxs)。

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

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

下面来分析一下，假设我们要把 (ls) 和 (rs) 合并到 (rt)。

(ls) 能看到的楼房合并之后也能看到。

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

我们把 (rs) 拆成两半，(s_1) 和 (s_2)。

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

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

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
", t[1].len);
    }
    return 0;
}

---

[\_EOF\_ ]