skyline问题

暴力写法(有错误的测试点)

坐标 $<10000$、建筑 $\le 5000$，直接开数组 h[10001]，每幢楼对 $[L,R)$ 逐格取 max（最多 $5000\times10000=5\times10^7$ 次操作，1s 内可过），再扫一遍输出跳变点。

#include <bits/stdc++.h>
using namespace std;
const int MAXC = 10005;
int h[MAXC];                       // h[x]: 单位区间 [x, x+1) 的轮廓高度
int main(){
    int L, H, R;
    while(cin >> L >> H >> R)      // 读到文件尾为止
        for(int x = L; x < R; x++) // 右端点开区间！
            h[x] = max(h[x], H);
    bool first = true;
    for(int x = 1; x < MAXC; x++)
        if(h[x] != h[x-1]){        // 跳变 => 折点 (x, h[x])
            if(!first) cout << " ";
            cout << x << " " << h[x];
            first = false;
        }
    cout << endl;
    return 0;
}

---

输出格式说明：题目要求"第奇数个数是折点 x、第偶数个数是折点 y"，即把折点序列拍平成一串用空格隔开的整数，上面的写法正好满足。

一、 核心思想：为什么要“乘 2”？

在天际线问题中，建筑覆盖的区间通常是左闭右开的 $[l, r)$。如果我们只用整数坐标来记录高度，就会遇到一个尴尬的问题：整数点 $x$ 的高度，和它右侧区间 $(x, x+1)$ 的高度可能不一样。

为了在整数数组中区分 “点” 和 “区间”，代码使用了位运算将所有坐标放大 2 倍：

• 偶数下标 2*i （即 i<<1）：代表整数坐标点 $i$ 本身的高度。
• 奇数下标 2*i+1 （即 i<<1|1）：代表开区间 $(i, i+1)$ 内部的高度（你可以理解为 $i+0.5$ 处的高度）。

通过这种映射，原本连续的实数轴被完美地离散化到了 maxh 数组中。

---

二、 逐段代码

1. 初始化与输入

int maxh[20005]; // 坐标最大10000，乘2后最大20000，开20005足够
int l,h,r,L=10005,R=0; // L和R记录所有建筑的最左和最右边界
while(scanf("%d%d%d",&l,&h,&r)!=EOF) {
    L=min(L,l);
    R=max(R,r);

• 作用：不断读入建筑的左边界 l、高度 h、右边界 r，直到文件结束（EOF）。同时维护全局的最左边界 L 和最右边界 R，为后续的输出划定范围。

2. 高度更新（核心）

    for(int i=l; i<=r; i++) {
        maxh[i<<1] = max(maxh[i<<1], h);       // 更新整数点 i 的高度
        if(i<r) maxh[i<<1|1] = max(maxh[i<<1|1], h); // 更新区间 (i, i+1) 的高度
    }

• i<<1：等价于 i*2，代表点 $i$。建筑覆盖了 $[l, r]$ 的所有整数点，所以点 $i$ 的高度要更新。
• i<<1|1：等价于 i*2+1，代表区间 $(i, i+1)$。
• if(i<r) 的玄机：建筑是左闭右开 $[l, r)$ 的。当循环到 $i=r$ 时，建筑在 $r$ 点已经结束，不应该覆盖它右侧的区间 $(r, r+1)$。因此，只有当 $i < r$ 时，才更新奇数下标（区间）的高度。这完美实现了右开边界的语义！

3. 折点检测与输出

for(int i=L; i<=R; i++) {
    // 判断1：点 i 的高度 与 左侧区间 (i-1, i) 的高度是否不同？
    if(maxh[i<<1] != maxh[(i<<1)-1]) 
        printf("%d %d ", i, maxh[i<<1]);
        
    // 判断2：点 i 的高度 与 右侧区间 (i, i+1) 的高度是否不同？
    if(maxh[i<<1] != maxh[i<<1|1]) 
        printf("%d %d ", i, maxh[i<<1|1]);
}

天际线的折点只可能出现在整数坐标 $x$ 处。在 $x=i$ 这个位置，代码检查了两次跳变：

1. 左侧跳变：如果点 $i$ 的高度 $\ne$ 它左边区间 $(i-1, i)$ 的高度，说明轮廓线在 $x=i$ 处发生了“左侧突变”。此时输出折点 (i, 点i的高度)。
2. 右侧跳变：如果点 $i$ 的高度 $\ne$ 它右边区间 $(i, i+1)$ 的高度，说明轮廓线在 $x=i$ 处发生了“右侧突变”（通常是建筑在这里结束了）。此时输出折点 (i, 右侧区间的高度)。

---

三、 用一个小例子跑一遍

假设有两个建筑：

1. [1, 11, 3] （左1，高11，右3）
2. [2, 6, 4] （左2，高6，右4）

第一步：更新 maxh 数组

• 处理建筑 1 [1, 11, 3]：
  • i=1: 更新 maxh[2](点1)=11, maxh[3](区间1~2)=11
  • i=2: 更新 maxh[4](点2)=11, maxh[5](区间2~3)=11
  • i=3: 更新 maxh[6](点3)=11。因为 i==r，不更新 maxh[7](区间3~4)。
• 处理建筑 2 [2, 6, 4]：
  • i=2: 更新 maxh[4](点2)=max(11,6)=11, maxh[5](区间2~3)=max(11,6)=11
  • i=3: 更新 maxh[6](点3)=max(11,6)=11, maxh[7](区间3~4)=6
  • i=4: 更新 maxh[8](点4)=6。不更新 maxh[9]。

此时的 maxh 数组状态（未提及的均为0）：

下标	0,1	2(点1)	3(区1-2)	4(点2)	5(区2-3)	6(点3)	7(区3-4)	8(点4)	9(区4-5)
值	0	11	11	11	11	11	6	6	0

第二步：检测跳变并输出 (L=1, R=4)

• i=1:
  • maxh[2](11) != maxh[1](0) $\Rightarrow$ 输出 1 11 (建筑1起步)
  • maxh[2](11) == maxh[3](11) $\Rightarrow$ 不输出
• i=2:
  • maxh[4](11) == maxh[3](11) $\Rightarrow$ 不输出
  • maxh[4](11) == maxh[5](11) $\Rightarrow$ 不输出
• i=3:
  • maxh[6](11) == maxh[5](11) $\Rightarrow$ 不输出
  • maxh[6](11) != maxh[7](6) $\Rightarrow$ 输出 3 6 (建筑1结束，高度降为建筑2的高度6)
• i=4:
  • maxh[8](6) == maxh[7](6) $\Rightarrow$ 不输出
  • maxh[8](6) != maxh[9](0) $\Rightarrow$ 输出 4 0 (建筑2结束，高度降为0)

最终输出：1 11 3 6 4 0。与天际线的真实折点完全一致！

---

这段代码是解决经典问题 “天际线 / 城市轮廓线（Skyline）” 的一种非常巧妙且优雅的解法。它没有使用复杂的扫描线或优先队列，而是采用了一种 “坐标放大法（乘2法）”，将“整数点”和“整数点之间的区间”离散化到一个一维数组中。

1. 极高的代码性价比：这段代码用最基础的数组和位运算，避开了 std::map、multiset 或复杂的离散化排序，时间复杂度为 $O(N \times \text{坐标范围})$，在坐标范围 $\le 10000$ 的题目中，运行速度极快且代码极短。
2. 位运算：i<<1 (乘2) 和 i<<1|1 (乘2加1) 是处理“点与区间”、“左孩子与右孩子”时的经典技巧，不仅执行效率高，而且让代码看起来非常紧凑。
3. 局限性：这种“坐标放大法”属于值域 hashing 的一种。它的前提是坐标的最大值不能太大。如果题目中坐标 $x$ 可以达到 $10^9$，那么 maxh 数组就开不下了