题解：P8246 [COCI2013-2014#3] ODAŠILJAČI

· · 题解

题目大意

在一个长度为 d 的二维城市中（像泰拉瑞亚那样），分布着 n 栋建筑。广播公司在其中的一些建筑上设有信号发射器。这些信号发射器发射的信号沿直线传播（不会散射、折射或反射），会完全被建筑阻挡或吸收。公司想要知道城市中具体有多少面积（即长度）的区域被信号发射器覆盖。

PS:上面这是来自官方原题面的描述，洛谷上面的题目将描述简化了。

思路

划分区域

我们会发现，n 栋建筑物 B_1,B_2,B_3, \dots B_n 把城市分割成了 n+1 段区域 A_0,A_1, A_2, \dots A_n。对于第 i 个区域 A_i，信号在这段区域的覆盖区域一定是由整个城市的全部建筑物决定的（这不废话吗？）。

既然对于区域 A_i，信号覆盖区域由全城建筑物所决定，那么换句话说，区域 A_i 的信号覆盖区域仅仅只和它左侧的 i 个建筑物和右侧的 n-i 个建筑物有关。

对于左侧的 i 个建筑物，如果不考虑右侧的 n-i 个建筑物，那么经过计算一定会在区域 A_i 或其右侧区域得到一个无信号覆盖区域变为信号覆盖区域的点，我把它称为覆盖起始点，我们可以记为 L_i。自 L_i 向右的区域都被信号覆盖。

如果左侧的 i 个建筑物的信号完全被某个高大的建筑物阻挡，或计算出来超出了区域的右侧端点，或干脆就没有信号发射器，这时我们可以把 L_i 看作是与该区域右侧的端点重合，相当于下面这样子：

同理，对于右侧的 n-i 个建筑物，如果不考虑左侧的 i 个建筑物，那么一定会在区域 A_i 或其左侧得到一个类似的覆盖起始点 R_i。若右侧的信号被阻挡或超出左侧端点，或干脆没有信号发射器，那么 R_i 可以取区域的左侧端点。

那么，我们就可以得到对于某个区域 A_i 来说，它的范围为 [from,to]，那么它的信号覆盖长度 area = to-from-\max(L_i-R_i,0)，相当于该区域的长度减去未覆盖信号区域长度。

因此，接下来的重点就是如何计算出每个区域的 L_i 和 R_i。

如何处理区域

遍历区域

我们已经知道，对于某个区域 A_i 来说，只要知道左侧的 i 个建筑和右侧的 n-i 个建筑，就可以知道该区域的信号覆盖区域长度。换句话说，如果我们有一个左侧的建筑序列 (B_1 , B_2 , \dots B_i)，那么最后被添加进这个序列的那一个建筑右侧的区域的 L_i 就可以由这个序列唯一计算得出。同理，如果我们有一个右侧的建筑序列 (B_{i+1} , B_{i+2} , \dots B_n)，也可以确定该序列左侧的第一个区域的 R_i。就像下面这样：

因此，我们可以同时从城市左端和右端分别向两边遍历建筑，构成左侧的建筑序列和右侧的建筑序列。对于每个序列，每次添加进去一个新建筑，就相应更新该序列右侧或左侧的第一个区域的 L_i 或 R_i。这样子，在遍历完所有建筑后，只需要统计每个区域的信号覆盖区域长度，答案就呼之欲出。

具体怎么添加一个建筑呢？我们以从左到右遍历为例。

添加一个建筑 B_i 总共分为两步：

  1. 添加建筑 B_i
  2. 计算 B_i 右侧区域 A_i 的 L_i。也就是：
building building_list[top_ref] = new_building;
top_ref++;
update_next_region(new_building);

因此难点在于如何计算 B_i 右侧区域的 L_i。

计算

要计算 B_i 右侧区域的 L_i，一个最暴力的做法是，枚举左侧建筑序列 (B_1 , B_2 , \dots B_i) 中的所有带有信号发射器的建筑。对于第 j 个建筑（如果有信号发射器）B_j，枚举建筑 B_{j+1} 到 B_i，然后计算 B_j 的信号受到 B_{j+1\sim i} 阻挡后对应在城市中的信号覆盖起始点 S_j。最后得出最终的 S_i。若 S_i 位于区域 A_i 内，那么就更新 L_i \gets S_i。

如何计算 S_j 呢？我们在从 B_{j+1} 到 B_{i} 遍历的过程中，设已经遍历到了建筑 B_k，我们会发现会发现要么信号没有被建筑 B_k 阻挡，S_j 不变。要么被阻挡，S_j 越来越大，因此 S_j 随着 k 增大必然是单调不减的。我们可以通过：

cover_begin_loc = max(get_cover_begin_location(building_list[i],building_list[j]),cover_begin_loc)

计算。至于函数 get_cover_begin_location(building transmitter,building barrier) 要如何实现，这就是个简单的几何问题：

但是这样子时间复杂度很大。遍历每个建筑总共 n 次，添加每个建筑需要枚举约 n^2 次，总共时间复杂度大约是 O(n^3)，可能连 48 分都拿不到。

那么该怎么做？我们会发现每次添加一个新的建筑，之前的建筑都会重复计算一遍信号覆盖起始点 S，这会耗费大量时间。因为对于一个建筑二元组 (B_j,B_k) 对应的 S_j，我们在添加 B_j 到序列时就已经计算完成。因此我们完全可以将之前对于 B_j 计算出的 S_j 存起来。添加新的建筑时，新的建筑 B_i 的 S_i 必然是其横坐标的值，然后更新一遍已有建筑的 S。这样子就可以省去枚举 B_{j+1\sim i} 的步骤。就是我们需要多出一个 double 数组 cover_begin_location[] 记录当前已添加建筑的信号覆盖起始点 S 。

同时，由于已经记录了每个信号发射器的信号覆盖起始点 S，自然也就没有保留没有信号发射器的建筑的必要，在添加新建筑的时候就不需要把没有信号发射器的建筑放进序列中。

于是我们就可以实现 update_next_region(new_building) 了：

void update_next_region(building now_building){
    double best_cover_begin_loc = regions[now_building.id].to;
    for(int i=stack_top_ref-1;i>=0;i--){
        double cover_begin_loc = building_list[i].location+get_cover_begin_location(building_list[i],now_building);
        if(cover_begin_loc>cover_begin_location[i]) cover_begin_location[i] = cover_begin_loc;
        else cover_begin_loc = cover_begin_location[i];
        if(cover_begin_loc<regions[now_building.id].from || cover_begin_loc>regions[now_building.id].to){
            continue;
        }
        if(cover_begin_loc<best_cover_begin_loc)
            best_cover_begin_loc = cover_begin_loc;
    }
    regions[now_building.id].cover_begin_l = best_cover_begin_loc;
}

以及 add(building new_building)：

void add(building new_building){
    if(new_building.has_transmitter){
        building_list[stack_top_ref] = new_building;
        cover_begin_location[stack_top_ref] = new_building.location;
        stack_top_ref++;
    }
    update_next_region(new_building);
}

于是就可以得出一种 O(n^2) 的做法，可以拿 48 分。

进一步优化

高度优化

遍历区域的 O(n) 不可能优化掉，因此关键点就在于，添加一个新的建筑，真的需要将已有序列中的所有建筑都更新一遍其信号覆盖起始点 S 吗？

我们容易发现，如果添加进来的新建筑 B_i 的高度 H_i 大于或等于已有序列中某些信号发射器的高度，那么已有序列中的这些信号发射器的信号将完全被阻挡。因此这些建筑是不需要更新甚至可以从序列中删除的。

如果每次添加新的建筑都删除一遍之前比它低的建筑，那么这个序列中所有信号发射器的高度必然是单调递减的。因此我们只需要将最新添加的建筑 pop() 掉，直到高度大于 H_i 的建筑停止，再将 B_i 添加进去即可（如果它有信号发射器的话）。也就是：

while(!empty()){
    if(top().height<= new_building.height) pop();
    else break;
}

最优信号发射器优化

我们还会发现，如果出现下面的情况，其中蓝色建筑是新遍历到的建筑 B_i，假设当前序列中最后一个建筑为 B_{top}：

也就是出现建筑 B_{top} 上的信号发射器的信号覆盖起始点 S_{top} 大于（或等于）它之前的建筑 B_{top-1} 上信号发射器的 S_{top-1} 的情况，这时候建筑 B_{top} 完全可以 pop() 掉，只保留第二个建筑 B_{top-1}。因为，很明显（你可以证明一下），无论之后添加进多少建筑，建筑 B_{top-1} 上的信号发射器的 S_{top-1} 所在横坐标总会小于等于 B_{top} 的 S_{top} 的横坐标，我们可以称这种情况为 B_{top-1} 比 B_{top} 更优。

当然，如果 pop() 掉 B_{top} 后，我们发现 B_{top-2} 比 B_{top-1} 还是更优，那同样可以 pop() 掉 B_{top-1}，直到最终序列的 B_{top^{'}-1} 和 B_{top^{'}} 满足 S_{top^{'}-1} > S_{top^{'}}，也就是 B_{top^{'}} 比 B_{top^{'}-1} 更优。而且在遍历过程中我们也可以顺带更新一遍遍历到的建筑的信号覆盖起始点 S。如下代码实现了这个过程：

const void update_ahead_buildings(building new_building){
    if(!empty()) cover_begin_location[top().id] = get_cover_begin_location(top(),new_building);
    if(stack_top_ref >1) cover_begin_location[second().id] = get_cover_begin_location(second(),new_building);
}
const void pop_invalid(building new_building){
    update_ahead_buildings(new_building);
    while(stack_top_ref>1){
        if(!is_valid(cover_begin_location[second().id],cover_begin_location[top().id])){
            pop();
            update_ahead_buildings(new_building);
        }else break;
    }
}

其中，函数 is_valid() 在从左到右遍历过程中是第二个参数比第一个参数大为 true ，在从右到左遍历过程中则反之。

这样子处理后，我们能保证在接下来计算区域的左信号覆盖起始点 L 时，位于 B_{top} 的信号发射器对应的信号覆盖起始点 S 是序列中最优的，因此甚至都不需要再遍历一遍整个序列，只需要检测 S_{top} 是否在区域 A_i 内即可。也就是如下代码：

void update_next_region(building now_building) override{
    regions[now_building.id].cover_begin_l = regions[now_building.id].to;
    if(!empty()){
        double cover_begin_loc = cover_begin_location[top().id];
        if(regions[now_building.id].is_in(cover_begin_loc)) 
            regions[now_building.id].cover_begin_l = cover_begin_loc;
    }
}

于是，我们成功地将 O(n^2) 的复杂度优化到了接近 O(n) 的复杂度。

最终AC代码

见https://www.luogu.com.cn/paste/nabrsg0j

其他的一些东西

你也可以在我的个人博客上看到这篇题解（对比后你会发现洛谷这篇题解已经做了比较大幅的修改）：https://blog.qiguaideaaaa.top/做题笔记：p8246-odasiljaci/。

另外这是我第一次在洛谷上发题解，有点紧张，如有疏漏还请见谅。