离散化
离散化目的是将较大区间的个体映射到较小的区间中,提升空间效率,常用来求当前位置的数在源序列的相对位置
for(int i=1;i<=n;++i){
t[i] = a[i];
}
sort(t+1,t+1+n);
end = unique(t+1,t+1+n)-t-1; // unique 返回去重后数组尾地址, end 为数组尾下标
for(int i=1;i<=n;++i){
a[i] = lower_bond(t+1,t+end+1,a[i])-t;// 在t中二分查找a[i] 再减去首地址 即可得到相对大小
}
题目: luogo P1496 火烧赤壁
- 题目大意: 给出(n)个线段,求覆盖长度
- 思路: 先将所有左右端点离散化,划分成有序的若干个区间,利用差分数组记录有效的位置,差分数组的前缀和大于零则更新该区间
#include<bits/stdc++.h>
#define ll long long
#define FOR(i,n) for(int i =1; i <= n;++i )
#define FOR0(i,n) for(int i =0; i < n;++i )
#define inf 0x3f3f3f3f
#define EPS (1e-8)
#define ALL(T) T.begin(),T.end()
using namespace std;
const int maxn = 5e5+40;
int n;
int t[maxn],a[maxn],b[maxn],add[maxn];
int main(){
cin >> n;
FOR(i,n){
cin >> a[i] >> b[i];
t[i*2-1] = a[i];
t[i*2] = b[i];
}
sort(t+1,t+1+n+n);
int m = unique(t+1,t+1+n+n)-t-1;
for(int i=1;i<=n;++i){
a[i] = lower_bound(t+1,t+m+1,a[i])-t;
b[i] = lower_bound(t+1,t+1+m,b[i])-t;
add[a[i]]++; //原从 a[i] 到 b[i] 加 1
add[b[i]]--;
}
int temp=0,ans=0;
FOR(i,m){
temp+=add[i];
// cout << add[i] << ' '<< t[i] << endl;
if(temp > 0){
// 当前区间可用,更新右端点
ans = ans + t[i+1] - t[i];
}
}
cout << ans << endl;
return 0;
}