# 基础算法模板之区间离散化与合并()-其他

## 基础算法模板之区间离散化与合并()

### 区间离散化

``````vector<int> alls; // 存储所有可能下标
sort(alls.begin(),alls.end()); // 排序
alls.erase(unique(alls.begin(),alls,end()),alls.end()); // 有序序列去重
// 根据x找到被映射后的下标
int find(int x)
{
int l = 0,r = alls.size() - 1;
while(l < r) // 二分搜索
{
int mid = l + r >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1; // 保证映射后的下标是从1开始
}
``````

### 区间合并

``````void merge(vector<pair<int,int>> &segs)
{
vector<pair<int,int>> res;
int st = -2e9,ed = -2e9;
for(auto seg : segs)
{
if(ed < seg.first)
{
if(st != -2e9) res.push_back({st,ed});
st = seg.first;
ed = seg.second;
}
else
{
ed = max(ed,seg.second);
}
}
if(st != -2e9) res.push_back({st,ed});
segs = res;
}
``````
————————

### 区间离散化

``````vector<int> alls; // 存储所有可能下标
sort(alls.begin(),alls.end()); // 排序
alls.erase(unique(alls.begin(),alls,end()),alls.end()); // 有序序列去重
// 根据x找到被映射后的下标
int find(int x)
{
int l = 0,r = alls.size() - 1;
while(l < r) // 二分搜索
{
int mid = l + r >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1; // 保证映射后的下标是从1开始
}
``````

### 区间合并

``````void merge(vector<pair<int,int>> &segs)
{
vector<pair<int,int>> res;
int st = -2e9,ed = -2e9;
for(auto seg : segs)
{
if(ed < seg.first)
{
if(st != -2e9) res.push_back({st,ed});
st = seg.first;
ed = seg.second;
}
else
{
ed = max(ed,seg.second);
}
}
if(st != -2e9) res.push_back({st,ed});
segs = res;
}
``````