洛谷P1496 火烧赤壁【题解】

时间：2023-01-16 22:11:28

事先声明

本题解文字比较多，较为详细，算法为离散化和差分，如会的大佬可以移步去别处看这道题的思路（因为作者比较懒，不想新开两个专题）。

题目简要

给定每个起火部分的起点和终点，请你求出燃烧位置的长度之和。
注意：左闭右开

浅浅来谈一下

看到这道题时，你肯定有很多疑问。

  • 为什么作者要搞左闭右开啊？

  • 有重复的区间怎么搞？

  • 我c， \(a\) 和 \(b\) 的范围在 \(-2^{31} \le a,b \le 2^{31}\) 之间？

光是这几个问题就可以把你难倒了吗？
不可能！我们先由简到繁，转换问题。

转换问题

有一段区间，范围为 \(0 \le 10^6\) ，其他的和原题一样。
我们在把问题抽象化。

问题描述

一段区间，每个点有 \(0,1\) 两个状态，初始每个点都是 \(0\) 。
每次操作选择一对 \(l,r\) ,将区间 \(l,r\) 变成 \(1\) ，问最后这一段区间 \(1\) 的个数？

因为题目的范围不支持我们进行 \(O(MAX\ a)\) 的遍历，所以，我们要想办法进行时间复杂度的优化，让他变成 \(O(1)\) 或 \(O(\log_a)\) 。

这样涉嫌区间问题，时间复杂度压缩的问题，可以考虑差分。

差分

绕过本题，我们看另外一题

问题描述：P2367 语文成绩

给定一对 \(n,p\) ，表示有 \(n\) 名同学，需要进行 \(p\) 次操作。
每次操作给定 \(x,y,z\) 表示从第 \(x\) 名同学到第 \(y\) 同学加上 \(z\) 的分数。
问全班最低分？
满足 \(1 \le n,p \le 5*10^6\)

浅浅谈一下

乍一看，第一反应就是暴力。
暴力遍历 \(x,y\) ，时间复杂度为 \(O(pn)\) ，明显支持不了。
这里考虑一种新的方法：差分。

我们设 \(cf_i=a_i-a_{i-1}\) ，特殊的，我们令 \(cf_1=a_1\) 。
明显的，我们会发现：

\[\begin{aligned} \sum_{i=1}^ncf_i&=a_1 + (a_2-a_1) + (a_3-a_2) + ....(a_n-a_{n-1})\\ &=a_n \end{aligned} \]

于是，我们发现了一个很重要的结论，差分数组的前缀和等于原数组。

我们在来看怎么修改。
我们把求原数组当成把差分数组从前往后扫一遍。

假设我们要修改 \([x,y]\) 的值，我们从前往后扫，扫到 \(x\) 前都没有问题，扫到了 \(x\) 了！诶，要加 \(w\) ，我们再次往后扫， \(y\) 前面也畅通无阻，但是扫到 \(y+1\) 的时候多了 \(w\) ，我们把他减掉，再往后扫，发现都没问题了，因为一加一减抵消了！

所以，我们可以归纳得：修改 \([x,y]\) 时， \(cf_x++\) ， \(cf_{y+1}--\) 。
所以，这道题我们就做出来了。

Code

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 5e6 + 7;

int n, p, a[MAXN], w[MAXN];

int main() {
	cin >> n >> p;
	for (int i = 1; i <= n; i ++) cin >> a[i], w[i] = a[i] - a[i - 1];
	for (int i = 1; i <= p; i ++) {
		int x, y, z;
		cin >> x >> y >> z;
		w[x] += z, w[y + 1] -= z;
	}
	int ans = 1e9, sum = 0;
	for (int i = 1; i <= n; i++) sum += w[i], ans = min(ans, sum);
	cout << ans << endl;
	return 0;
}

回到抽象化的问题

我们重新看这题，是不是很简单了？这不就是差分的模板嘛。
我们按照刚才的处理方法处理一遍，求下前缀和，看看哪些是 \(1\) 统计就行。

回到原题

我们可以发现，我们刚才一个很重要的元素就是：差分数组。
但是原题是： \(-2^{31} \le a,b \le 2^{31}\) ，怎么搞数组？
这里就要用到另外一种方法：离散化。

又离开本题(QwQ)

问题描述：

给定一串数，求出每个数在数列中的排名。
满足 \(-10^9 \le a_i \le 10^9\) 。

又浅浅谈一下(TwT)？

我们发现问题求的是排名，很容易发现，排名符合两个性质。

  1. 把很大的区间映射到很小的区间。
  2. 原数组每两个元素的大小关系不变。

只要遇到的问题符合这种性质，我们就考虑用离散化。

离散化三部曲

  1. 排序
    一定要排序！！因为后面的函数需要排序，时间为 \(O(n\log_n)\) ，这里不考虑值域（你看看值域多大？）
  2. 去重
    使用 \(unique\) 函数，使用格式： \(unique(a.begin(),a.end())\) 这里 \(a.begin(),a.end()\) 分别指数组的头指针和尾指针，普通数组用 \(a+1,a+1+n\)
    注意一点：该函数的返回值是不属于去重数组的第一个地址，比如有个数组长度为 \(n\) ，去重数组长度为 \(k\) ，他的返回值就是 \(a_{k+1}的地址\)。
    根据上面几点，我们可以推出公式。

\[k=unique(a+1,a+1+n)-(a+1) \]

这样我们就可以求出去重数组的长度了。
3. 求名次了
我们这里了解一个函数： \(lower_\ bound(a+1,a+1+n,x)\) 他返回的是第一个大于等于 \(x\) 的元素的地址，注意：必须有序。
于是我们就可以推出一个公式：（ \(rk\) 数组为名词数组）。

\[rk[i] = lower_\ bound(b + 1, b + 1 + k, a[i]) - b; \]

\(b\) 数组为去重数组， \(a\) 数组为原数组（应该可以理解吧……）。

至此，第二个分任务已经完成。

Code：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 7;

int T, a[MAXN], b[MAXN], rk[MAXN];

int main() {
	for (cin >> T; T; T--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		memcpy(b + 1, a + 1, n * sizeof(int));
		
		sort(b + 1, b + 1 + n);
		int *ed = unique(b + 1, b + 1 + n);
		for (int i = 1; i <= n; i++) {
			rk[i] = lower_bound(b + 1, ed, a[i]) - (b + 1) + 1;
			cout << rk[i] << ' ';
		}
		cout << endl;
	}
	return 0;
}

再一次回到原题

我们有离散化，差分，天下不就容易打了吗？(bushi)

最后一次浅浅谈一下

我们考虑把读进来的 \(2n\) 个数全部进行离散化（先别问为什么）。
这样就会形成 \(2*n-1\) 个区间，我们把每一个区间当成一个元素进行差分。
比如 \(1\) 和 \(2\) 中间是 \(1\) 区间，所以要更新 \([l,r]\) 时，就是更新 \([l,r-1]\) 个区间，具体的：

\[cf_l++,cf_r-- \]

最后，求出前缀和，若第 \(i\) 区间之间是 \(\ge 1\) 的，就把 \(b[i+1] - b[i]\) 累加到 \(ans\) 里就行。
所以，这道题我们就做完了。
但是真的做完了吗？

question1

  • 边界条件考虑了吗？
    既然是左闭右开，右边的就不算。
    刚刚我在讲的时候快速忽略了一个点，为什么区间的长度为 \(b[i+1]-b[i]\) ，不是 \(b[i+1]-b[i]+1\) 吗？
    我们来举一个例子：
    区间 \([2,7)\) 分为 \([2,4),[4 7)\) 他们的和是不是相等的。
    为什么举这个例子呢？如果你认真去做这道题目，发现离散化把他们拆成许多个小的区间，要把他们加起来凑成一个大区间，所以我才举了这个例子。
    可以发现 \([2,7)\) 为 \(2,3,4,5,6\) ，而 \([2,4),[4 7)\) 为 \(2,3,\ 4,5,6\) 发现是完全一样的，所以作者左闭右开是帮助我们更好的写代码（谢谢~~）

question2

这是一个扩展，有什么公式可以用 \(b\) 和 \(rk\) 表示 \(a\) 吗？
这里是有的，这里给出公式。

\[b[rk[i]]=a[i] \]

至于证明，请读者（包括以后的我）自己思考，如果想不会请在评论区打出来，我会解答。

Code

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e4 + 7;

int n, a[2 * MAXN], b[2 * MAXN], rk[2 * MAXN], cf[2 * MAXN], cnt;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for (int i = 1; i <= n; i ++) 
		cin >> a[++ cnt], cin >> a[++ cnt];
	
	memcpy(b + 1, a + 1, 2 * n * sizeof(int));
	sort(b + 1, b + 1 + 2 * n);
	int k = unique(b + 1, b + 1 + 2 * n) - (b + 1);

	for (int i = 1; i <= 2 * n; i++) 
		rk[i] = lower_bound(b + 1, b + 1 + k, a[i]) - b;
	for (int i = 1; i <= 2 * n; i += 2) {
		int r =rk[i + 1], l = rk[i];
		cf[l] ++, cf[r] --;
	}
	int ans = 0, sum = 0;
	for (int i = 1; i <= k; i++) {
		sum += cf[i];
		if (sum > 0) ans += b[i + 1] - b[i];
	}
	cout << ans;
	return 扶苏咕咕咕~~~;
}

完结撒花✿✿ヽ(°▽°)ノ✿

相关文章