#题解#洛谷P1496#离散化#

[传送门](P1496 火烧赤壁 - 洛谷)

分析

1. a,b的范围在 - 2 ^ 31 到 2 ^ 31 ，直接开数组用桶来记录每一个点是否染色显然MLE / RE

2. 尝试开数组用桶记录一个个区间段是否染色，如何选择区间段的端点呢？

显然，只需选取每次染色操作区间的端点即可完成我们的要求。

3. 用x[N]数组从小到大记录每次染色操作区间的端点（需要离线处理）

c[N]数组记录一个个区间段: c [ i ] 为 [ x [ i ] , x [ i + 1 ] ] 的染色情况

4. 每次染色操作用二分查找 ai 与 bi 在 c [ N ] 中的位置，更新c [ pos a] ----- c [ pos b ]为1即可

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N], b[N], x[N], book[N];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin >> n;int j = 1;for (int i = 1; i <= n; i++){cin >> a[i] >> b[i];x[j++] = a[i];x[j++] = b[i];}sort(x + 1, x + j);for (int i = 1; i <= n; i++){int pos1 = lower_bound(x + 1, x + j, a[i]) - x;//lower_bound是STL中的二分查找，返回的是第一个大于等于a[i]的数的地址int pos2 = lower_bound(x + 1, x + j, b[i]) - x;for (int k = pos1; k < pos2; k++)book[k] = 1;//若book[pos]==1:x[pos]_x[pos+1]染色}int ans = 0;for (int i = 1; i < j; i++ )if (book[i])ans += x[i + 1] - x[i];cout << ans;return 0;
}