离散化
题单 🧑🏻💻
| 题目来源 | 题目名称 | 题目链接 | 备注 | 难度 |
|---|---|---|---|---|
| Acwing - 802 | 区间和 | 链接🔗 | 离散化模版题 | 🟢 |
| HDU - 2199 | 链接🔗 | 🟡 | ||
| HDU - 2199 | 链接🔗 | 🟡 |
题解 🚀
区间和
题目信息 📚
【题目名称】Acwing - 802 - 区间和
【题目描述】
假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 $n$ 次操作，每次操作将某一位置 $x$ 上的数加 $c$。
接下来，进行 $m$ 次询问，每个询问包含两个整数 $l$ 和 $r$，你需要求出在区间 $[l,r]$ 之间的所有数的和。
【输入】
第一行包含两个整数 $n$ 和 $m$。
接下来 $n$ 行，每行包含两个整数 $x$ 和 $c$。
再接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$。
【输出】
共 $m$ 行，每行输出一个询问中所求的区间内数字和。
【数据范围】
$−10^9 \le x \le 10^9$
$1\le n,m \le 10^5$
$−10^9 \le l \le r \le 10^9$
$−10000 \le c \le 10000$
【输入样例】
3 3
1 2
3 6
7 5
1 3
4 6
7 8【输出样例】
8
0
5【原题链接】
https://www.acwing.com/problem/content/804/
题目解析 🍉
【题目分析】
数据扩大版的区间和查询，使用一般采用离散化的前缀和解决。
【C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 3e5 + 10;
int n, m, x, c, l, r;
vector<PII> adds; // 存储添加操作
vector<PII> q; // 存储查询操作
vector<int> s; // 存储离散点
int sum[N]; // 存储前缀和
// 离散化查询操作
int findi(int x) {
return lower_bound(s.begin(), s.end(), x) - s.begin() + 1;
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n >> m;
// 存储添加操作
for (int i = 1; i <= n; ++i) {
cin >> x >> c;
adds.push_back({x, c});
s.push_back(x);
}
// 存储查询操作
for (int i = 1; i <= m; i++) {
cin >> l >> r;
q.push_back({l, r});
s.push_back(l), s.push_back(r);
}
// 离散化
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
// 离散化后执行添加操作
for (int i = 0; i < adds.size(); ++i) {
x = findi(adds[i].first);
sum[x] += adds[i].second;
}
// 离散化的前缀和求和
for (int i = 1; i < N; i++) {
sum[i] += sum[i - 1];
}
// 离散化后进行查询操作
for (int i = 0; i < q.size(); ++i) {
l = findi(q[i].first), r = findi(q[i].second);
cout << sum[r] - sum[l - 1] << endl;
}
return 0;
}D - Online games
题目信息 📚
【题目描述】
There is an online game with $N$ registered players.
Today, which is the $10^{100}$-th day since its launch, the developer Takahashi examined the users’ login history. It turned out that the $i$-th player logged in for $B_i$ consecutive days from Day $A_i$, where Day $1$ is the launch day, and did not log in for the other days. In other words, the $i$-th player logged in on Day $A_i$, $A_i+1$, $\ldots$, $A_i+B_i-1$, and only on those days.
For each integer $k$ such that $1\leq k\leq N$, find the number of days on which exactly $k$ players logged in.
【输入】
Input is given from Standard Input in the following format:
N
$N$
$A_1$ $B_1$
$A_2$ $B_2$
$:$
$A_N$ $B_N$
【输出】
Print $N$ integers with spaces in between, as follows:
$D_1$ $D_2$ $\cdots$ $D_N$
Here, $D_i$ denotes the number of days on which exactly $k$ players logged in.
【数据范围】
- $1 \leq N \leq 2\times 10^5$
- $1 \leq A_i \leq 10^9$
- $1 \leq B_i \leq 10^9$
- All values in input are integers.
【输入样例1】
3
1 2
2 3
3 1【输出样例1】
2 2 0【输入样例2】
2
1000000000 1000000000
1000000000 1000000000【输出样例2】
0 1000000000题目解析 🍉
【题目分析】
本题题面抽象后，就是分析若干区间的重叠情况。
可以把每个区间进行离散，只记录起点与终点，如区间 [4, 8] 离散为：
- pair{4, +1} → 起点，坐标为4
- pair{8, -1} → 终点，坐标为8
将所有点放入 vector 中进行排序。
设定一个 cnt 变量记录当前区间重合数，然后两点两点逐段分析。
- 若
v[i].second == 1，说明有一个区间开始，重叠数 +1 - 若
v[i].second == 0，说明有一个区间结束，重叠数 -1
PS：在统计时，设定起点是「闭」，终点是「开」，有利于统计。
本题思路非常精妙，值得学习。
【C++代码】点排序法 ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int ans[N], n, s, e;
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n;
vector<pair<int, int>> v;
for (int i = 1; i <= n; ++i) {
cin >> s >> e;
// 将一个区间离散为起点和终点
v.push_back({s, +1});
v.push_back({s + e, -1});
}
// 对所有点排序
sort(v.begin(), v.end());
// 从第1个点开始，不断对相邻两点v[i],v[i+1]进行处理
int cnt = 0; // cnt记录当前重合的区间数量
for (int i = 0; i < v.size() - 1; i++) { // 共有v.size()个点，v.size()-1段
cnt += v[i].second; // cnt根据当前点类别改变，如当前点为起点，说明有一个新区间加入；反之，有一个区间结束
ans[cnt] += v[i + 1].first - v[i].first; // 记录v[i]和v[i+1]之间的区间重叠情况
}
// 输出答案
for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
return 0;
}火烧赤壁
题目信息 📚
【题目名称】洛谷P1496 - 火烧赤壁
【题目描述】
曹操平定北方以后，公元 208 年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。
孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。
隆冬的十一月，天气突然回暖，刮起了东南风。
没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。
曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！
【输入】
第一行一个整数，表示起火的信息条数 $n$。
接下来 $n$ 行，每行两个整数 $a, b$，表示一个着火位置的起点和终点（注意：左闭右开）。
【输出】
输出一行一个整数表示答案。
【数据范围】
对于全部的测试点，保证 $1 \leq n \leq 2 \times 10^4$，$-2^{31} \leq a \leq b \lt 2^{31}$，且答案小于 $2^{31}$。
【输入样例】
3
-1 1
5 11
2 9【输出样例】
11【原题链接】
https://www.acwing.com/problem/content/804/
题目解析 🍉
【题目分析】
本题和上题（AtCoder ABC221D）可以采用相同的做法，只不过在最后统计答案时，不需要统计数轴上区间重合数，而是统计数轴上有被区间覆盖的点的个数即可（即 cnt>=1）。
PS：在统计时，设定起点是「闭」，终点是「开」，有利于统计。
【C++ 代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
vector<PII> a; // 存储离散点
int n, l, r;
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n;
// 将区间离散为起点与终点
for (int i = 1; i <= n; ++i) {
cin >> l >> r;
a.push_back({l, +1}), a.push_back({r, -1});
}
// 离散点排序
sort(a.begin(), a.end());
// 统计答案
int cnt = 0, res = 0;
for (int i = 0; i < a.size() - 1; i++) {
cnt += a[i].second;
if (cnt) res += a[i + 1].first - a[i].first;
}
cout << res << endl;
return 0;
}
