ACDream(18)DisappearingBlocks:离散化与二分查找

### 题目链接
- [点击访问](#)

### 背景描述
在解决ACDream (18) Disappearing Blocks的问题时，我们将给定的图形视作一系列波动。具体来说，当波峰被水淹没时，图形的部分数量会减少；相反，当波谷被水淹没时，部分数量会增加。基于这一特性，解题的关键在于准确识别并处理所有的波峰和波谷。

### 解题思路
为了有效地处理波峰和波谷，我们首先对图形的两端点进行特殊处理，通常通过将`h[0]`和`h[n+1]`设定为-1来实现。接下来，提取所有波峰和波谷的高度，并按高度降序排列这些点。在遍历这些点时，需要注意的是，对于具有相同高度但非连续的点，应将它们作为一个整体进行处理，确保每次高度变化时的计算结果是正确的。

### 实现细节
1. **数据预处理**：初始化边界条件，并读取输入数据。
2. **波峰波谷识别**：遍历数组，确定每个波峰和波谷的位置。
3. **排序与处理**：将波峰波谷按高度降序排序，并依次处理，确保正确计算每种情况下的部分数量。
4. **二分查找**：使用二分查找算法快速定位特定高度对应的答案。

### 代码示例
```cpp
#include
#include
#define MAX 1000000+10
using namespace std;

int h[MAX];
int Q[MAX];
int res[MAX];
struct Node {
int height;
bool isPeak;
};

bool compare(Node a, Node b) {
return a.height > b.height;
}

int binarySearch(Node a[], int len, int target) {
int left = 0, right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid].height == target) return mid;
else if (a[mid].height else left = mid + 1;
}
return right;
}

int main() {
int T;
cin >> T;
for (int cas = 1; cas <= T; ++cas) {
int n, m;
cin >> n >> m;
h[0] = h[n + 1] = -1;
for (int i = 1; i <= n; ++i) cin >> h[i];

vector peaksAndValleys;
for (int i = 1; i <= n; ++i) {
if ((h[i] > h[i - 1] && h[i] > h[i + 1]) || (h[i] peaksAndValleys.push_back({h[i], h[i] > h[i - 1]});
}
}

sort(peaksAndValleys.begin(), peaksAndValleys.end(), compare);
int currentParts = 1;
for (const auto& point : peaksAndValleys) {
if (point.isPeak) --currentParts;
else ++currentParts;
res[point.height] = currentParts;
}

cout <<"Case #" < for (int i = 0; i int query;
cin >> query;
int index = binarySearch(peaksAndValleys.data(), peaksAndValleys.size(), query);
cout <<(index >= 0 ? res[peaksAndValleys[index].height] : 0) <<' ';
}
cout < }
return 0;
}
```
### 结论
通过上述方法，我们可以高效地解决Disappearing Blocks问题，利用离散化和二分查找技术，确保了算法的效率和准确性。