题解：楼房可见性问题

问题重述

小A站在坐标原点(0,0)，观察x轴正方向上的一系列楼房。第i栋楼房位于x=i处，高度为Hi，用线段连接(i,0)和(i,Hi)表示。每天施工队会修改某栋楼的高度，需要每天计算当前可见的楼房数量。

可见性定义：一栋楼可见，当且仅当从原点出发的视线（直线）不被任何前面的楼房阻挡。

关键性质

1. 斜率决定可见性：楼i可见的条件是其斜率Hi/i严格大于前面所有可见楼的斜率。
2. 单调递增序列：可见楼序列的斜率构成严格递增序列。
3. 动态维护：每天修改一个楼的高度，需要快速重新计算可见数量。

算法设计

线段树解法：
1. 节点信息：
• mx：区间最大斜率
• len：区间内可见楼数量（即斜率严格递增序列长度）

1. 核心操作：
   • 修改：单点更新楼高，重新计算斜率。
   • 查询：求全局可见楼数量，即根节点的len。

2. 关键技巧：
   • 特殊pushup：合并子区间时，右区间的可见楼数量取决于左区间最大值（类似单调栈思想）。
   • 剪枝优化：利用区间最大值快速跳过无效计算。

代码解析

#include<bits/stdc++.h>
using namespace std;
const int N=100000+10;
int n,m;
double a[N]; // 存储每个位置的斜率

struct node{
    double mx; // 区间最大斜率
    int len;   // 区间可见楼数量
}t[4*N];

// 标准区间最大值合并
void pushup1(int x) {
    t[x].mx = max(t[x<<1].mx, t[x<<1|1].mx);
}

// 计算在斜率必须>lx的条件下，该区间的可见楼数量
int pushup2(double lx, int x, int l, int r) {
    // 剪枝1：整个区间最大值都不够大
    if(t[x].mx <= lx) return 0;
    // 剪枝2：左端点已经足够大，直接返回整个区间值
    if(a[l] > lx) return t[x].len;
    // 叶子节点直接判断
    if(l == r) return a[l] > lx;

    int mid = (l+r)>>1;
    // 如果左半最大值不够大，只处理右半
    if(t[x<<1].mx <= lx) 
        return pushup2(lx, x<<1|1, mid+1, r);
    // 否则左半贡献+右半在左半最大值限制下的贡献
    else 
        return pushup2(lx, x<<1, l, mid) + (t[x].len - t[x<<1].len);
}

// 更新操作
void chan(int x, int l, int r, int to, int c) {
    if(l == r && l == to) {
        a[l] = (double)c/to; // 计算新斜率
        t[x].mx = a[l];
        t[x].len = 1; // 单楼必定可见
        return;
    }
    int mid = (l+r)>>1;
    if(to <= mid) chan(x<<1, l, mid, to, c);
    else chan(x<<1|1, mid+1, r, to, c);
    // 先更新最大值
    pushup1(x);
    // 再更新可见数量
    t[x].len = t[x<<1].len + pushup2(t[x<<1].mx, x<<1|1, mid+1, r);
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        int x, y;
        scanf("%d%d",&x,&y);
        chan(1, 1, n, x, y);
        printf("%d\n",t[1].len); // 输出全局可见数
    }
    return 0;
}

复杂度分析

• 时间复杂度：每次修改操作需要O(log n)时间进行更新，pushup2操作由于剪枝均摊也是O(log n)，总复杂度O(m log n)。
• 空间复杂度：O(n)存储线段树。

思考过程

1. 暴力思路：每次修改后重新扫描所有楼，O(nm)超时。
2. 单调性观察：发现可见性由斜率严格递增决定，类似维护单调栈。
3. 线段树优化：
   • 将问题转化为区间合并问题
   • 设计特殊pushup操作利用单调性剪枝
4. 实现技巧：
   • 维护区间最大值快速剪枝
   • 递归计算受限条件下的可见数量

为什么这样设计？

1. 线段树选择：需要支持动态修改和快速查询整体性质。
2. 特殊pushup：普通线段树无法直接维护此类信息，需要定制合并策略。
3. 剪枝优化：利用区间最大值避免不必要的递归，保证效率。

典型样例

输入：

4 3
1 2
2 4
3 1

处理过程：
1. 修改x=1，高度2 → 斜率2.0，可见[1]
2. 修改x=2，高度4 → 斜率2.0，被1阻挡，可见[1]
3. 修改x=3，高度1 → 斜率0.33，被1阻挡，可见[1]

总结

本题展示了如何将几何性质转化为数据结构问题，通过：
1. 分析问题本质（斜率单调性）
2. 设计定制化的线段树操作
3. 利用剪枝优化保证效率

这种区间合并+剪枝的思路，适用于许多需要维护特殊序列性质的问题。关键在于发现问题的合并规律并设计高效的合并策略。