《洛谷深入浅出进阶篇》 P1496火烧赤壁——初识离散化

上链接：

P1496 火烧赤壁 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1496上题干：

有一组序列，[-2^31,2^31] ， 现在给你n次操作，每一次操作给出两个整数l，r，代表一个子区间的左端点和右端点，[l,r）这就算覆盖一次。求所有的被覆盖的区间的长度

 例如：现在有一个序列：

给你三对数字，代表着区间的左端点和右端点，你分别对这些区间进行染色：

[1，3） 

[ 2，6）

[4，8) 

可以求出，经过这三次操作，被覆盖的区间的长度：

由于数据很小，所以我们可以用数组标记法：

枚举每次给出的区间，我们将区间内的数字打上标记，然后计算所有被打上标记的数有多少个就行了。

可以求出一共7个格子被覆盖了。

那么假如我给出以下的数据，数组标记法还能用吗？

[-2^31,-2^16)

[-65462131,-16846952)

[0,465)

[241,1321464)

[32137946,2^31)

首先，我们可以看出来，数组标记法，一定是行不通的。

首先数组下标是不能为负数，另外，数据达到了2^31，远远超出了数组能开辟的空间。

时空复杂度也是个惊人数字。

所以我们必须想办法来优化我们的思路。

其实

对于我们每一个给出的区间，

它们被覆盖的长度就是（右端点-左端点）

只不过有些区间是互相有一部分覆盖了而已。

那么应该怎么办呢？

有些人可能会想，我们只要计算出总长度，然后减去一次重复的区域。

这样或许可以，但，我们可以从根本入手

我们只需要想办法将这些会重复计算的地方只计算一次，那么问题就迎难而解了。

怎么才能只计算一次？————单元化计算（其实这也就是数组标记的思想）

还是上面那个例子：

给出三对区间

第一对区间：[1，3）

找到这个区间的两个端点：1，3

将 [1,3) 所在的区间打上标记（别忘记左闭右开）

也就是,  1  , 2 被打上了标记（这标记有什么用，后面就知道了）

第二对区间：[2，6) 

找到这个区间的端点：2，6

将 [2,6) 所在的区间打上标记

也就是,  2，3，4，5  被打上了标记

第三对区间:[4,8)

依次类推：

那么被打上标记的数字就是这些：

-3  -2 -1  0  1  2  3  4  5  6  7  8 9 10 11 

我们只要对所有打上标记的数字进行一项操作：ans = a[i+1] - a[i]   （差分的思想）

并将这个操作累加起来:ans += a[i+1] - a[i]   

ans = 2-1 + 3-2  + 4-3 + 5-4  + 6-5 + 7-6  + 8-7 = 7

这样的话，我们就不需要考虑会不会有重复区间的情况了，因为所有的数据只算了一遍

到这里，可能有些人坐不住了，你这有啥用啊，这么麻烦，还不如我直接手算呢。

欸，别急，这些只是小数据罢了，等到它是大数据的时候，就很有效果了。

另外，这样的操作，虽然看上去复杂，但是很好实现啊，你难道没发现每一步都是程序化的步骤么，所以有时候我们要站在电脑的角度去思考，瞪眼法虽好，但是很难以用程序来实现。

所以我们就可以引入离散化了（排序，去重，二分查找），

将每一对区间的左右端点当成一个个散点，将其放入数组里面：（这里不清楚的就去看看离散化的概念，很简单的，等你明白离散化是啥了之后再回来看看）

一共六组数字

[-2^31,-2^16)

[-65462131,-16846952)

[0,465)

[241,1321464)

[32137946,2^31)

将这一串数字进行排序:

紧接着把这个数组进行去重：（本组数据没有重复的，所以忽略） 

离散化的最后一步就是二分查找数据的位置。

并结合我们刚刚说过的概念：单元化处理。

还记得单元化处理的第一步是什么吗？（翻上去看看）

找到第一对区间的端点在数组中的位置：（用二分查找找端点，这也就是为什么我们要去重的原因）

第一对端点：-2^31,   -2^16

可以用lower_bound()来进行二分

也可以用手动二分查找

得到位置：1,4

所以我们给[1,4)打上标记（不知道为啥打标记的翻上去看那个更简单的例子，再简单描述一下就是为了方便一项一项地处理,并且所有的数只会计算一次，不信的话你随便写几对数字模拟一下）

打标记：flag[i]=1

以此类推。

最后一步就是单项求和：

如果这个数字被打上了标记，那么我们就进行单元化处理 ans+= a[i+1] - a[i]

最后输出ans就好了

上代码：

const int N = 2e4 + 10;
int n, l[N], r[N], flag[2 * N], temp[2 * N], a,b ;
long long fn[2 * N], ans;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> l[i] >> r[i];
		temp[++a] = l[i];
		temp[++a] = r[i];
	}
	sort(temp + 1, temp + 1 + a);
	for (int i = 1; i <= a;i++)
	{
		if (i == 1 or temp[i] != temp[i - 1])fn[++b] = temp[i];
	}
	for (int i = 1; i <= n; i++)
	{
		int L = lower_bound(fn + 1, fn + 1 + b, l[i]) - fn;
		int R = lower_bound(fn + 1, fn + 1 + b, r[i]) - fn;
		for (int j = L; j < R; j++)
			flag[j] = 1;
	}
	for (int i = 1; i < b; i++)
		if (flag[i])ans += fn[i + 1] - fn[i];
	cout << ans;
}