【题解】洛谷P1496 火烧赤壁 （离散化）

P1496 火烧赤壁 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

我们首先先看数据，n<=20000，数据不多，但是范围大（-10^9<=Ai,Bi<=10^9），这时，就可以用离散化了。但是在这里我们会遇到区间重合的问题（也可以使用区间合并），如下图

本题的题意是让我们求出燃烧位置的长度之和。区间重合时只需要区间最大数减去最小数字，那么我们如何获得这个数字呢？

朴素的想法是，在面对一段连续的区间时，从边界一直枚举下去到尽头用if语句终止。当我们离散化后，也不会有数组长度的问题了。对于连续区间，我们会考虑差分和前缀和。但是，如果如何区分左边界和右边界呢？

我的想法是，我们只需要[l+1,r]之间的区间进行操作，这样求前缀和后，sum[l]就是0，其他都大于0。

直接看代码吧qwq

/* P1496 火烧赤壁
 * 作者: Yukie
 * 日期: 2023-12-24
 * 算法: 离散化（map方法）
 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int maxn = 2e4 + 5;
vector<PII> fire;
map<int, int> h;
int n, Map[2 * maxn], sum[2 * maxn];
LL ans;

int find(int value) {
	for (map<int, int>::iterator it = h.begin(); it != h.end(); it++) { 
		if (it->second == value)
			return it->first;
	}
} //由离散化后的结果找原来的数，因为key本身就唯一，映射后也是从1升序，所以key和value均唯一

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		fire.push_back({l, r});
		h[l] = 1, h[r] = 1;
	}

	//h[x]就是离散化后的结果，已排好序
	int idx = 1;
	for (auto &t : h) { // 使用auto修改map值时，需要添加引用符号&
		t.second = idx;
		idx++;
	}

	for (auto fi : fire) {
		int x = h[fi.first], y = h[fi.second];
		Map[x + 1]++, Map[y + 1]--; //差分,为什么是左边界+1呢？为了到时候查找时能区分出来左右，实际上问题转为[l+1,r]
	}

	for (int i = 1; i <= h.size(); i++)
		sum[i] += sum[i - 1] + Map[i]; //前缀和

	int l, r; //不为0的区间的左端点和右端点。

	for (int i = 1; i <= h.size(); i++) {
		if (sum[i] != 0 && sum[i - 1] == 0)  //查找连续着火区间的左边界
			l = i - 1;
		if (sum[i] != 0 && sum[i + 1] == 0) {
			r = i;  //查找连续着火区间的右边界
			ans += find(r) - find(l);
			//由于这是离散化后的区间长度，并不是真正的区间长度，所以我们要找到原来的l与r，将他们相减，就是原来的区间长度。
		}
	}
	cout << ans << endl;
	return 0;
}

样例解释：

输入区间排序后：-1 1 2 5 9 11

映射后:1 2 3 4 5 6

差分数组：0 1 -1 1 1 -1

前缀和数组：0 1 0 1 2 1

不用map的离散化版本：

（待补）