离散化

按照我自己的理解，离散化就是反向的hash（哈希）

其实就是一种hash

通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题，即离散化。（摘自OIwiki）

STL中有现成

1
2
3
4
5
6
7
8
9
// a[i] 为初始数组,下标范围为 [1, n]
// len 为离散化后数组的有效长度
std::sort(a + 1, a + 1 + n);

len = std::unique(a + 1, a + n + 1) - a - 1;  //去重
// 离散化整个数组的同时求出离散化后本质不同数的个数。
std::lower_bound(a + 1, a + len + 1, x) - a;  // 查询 x 离散化后对应的编号


1
2
3
4
5
6
7
8
// std::vector<int> a, b; // b 是 a 的一个副本
std::sort(a.begin(), a.end());
a.erase(std::unique(a.begin(), a.end()), a.end());
for (int i = 0; i < n; ++i)
  b[i] = std::lower_bound(a.begin(), a.end(), b[i]) - a.begin();



但在此不提

代码实现离散化

实际上只要解决两个问题

  1. a[]中可能有重复元素
  2. 如何求出x离散化后的值（二分）

重复元素问题可以unique解决

而离散化后的值便如下二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

vector<int> alls; //存储所有待离散化的值
sort(alls.begin(),alls.end()); // 将所有制排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());

int find(int x) //找到第一个大于等于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 r + 1;
}

区间合并

若两个区间有交集，便把两个区间合并为一个区间（从思路上来看，这何尝不是一种贪心呢？）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
	vector<PII> res;

	sort(segs.begin(), segs.end());

	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;
}