【基础算法】离散化

离散化

// 每日一题
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, m;
int a[N], d[N], s[N], t[N];
long long b[N];

bool check(int x)
{
	memset(b, 0, sizeof b);
	for (int i = 1; i <= x; i++)
	{
		b[s[i]] += d[i];
		b[t[i] + 1] -= d[i];
	}
	
	for (int i = 1; i <= n; i++) b[i] += b[i - 1];
	
	for (int i = 1; i <= n; i++)
	{
		if (b[i] > a[i]) return false;
	}
	
	return true;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++)
	{
		cin >> d[i] >> s[i] >> t[i];
	}
	if (check(m))
	{
		cout << 0 << endl;
		return 0;
	}
	int l = 1, r = m;
	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	cout << -1 << '\n' << l << endl;
	return 0;
}

为什么要进行离散化？

假如给你一个序列，他的数据范围是 \(-10^9\) ~ \(10^9\) 你要统计它给出的数的个数，你能开数组来存嘛？

那么这样我们就可以讲这么大范围的数给映射到小范围的数里，打个比方，\(-1230384328\) 这个数就可以映射到 \(3\) 那么我们的 \(a[3]=-1230384328\) 我们统计的时候直接 \(cnt[3]++\)

离散化的几个问题

• 我们怎么快速的映射，并且让映射的数字相互之间不冲突？

  • 排序加去重，使序列升序的排到数组中

• 我们怎么找到映射后的数字在映射数组的下标？

  • 二分（已经排序了）、哈希表

例题：区间和

// 二分
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
vector<int> alls; // 存离散化之后的值
vector<PII> add, query;
int a[N], s[N];
int n, m;

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 - 1;
		else l = mid + 1;
	}
	return r + 1; // 下标从1开始
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		int x, c;
		cin >> x >> c;
		alls.push_back(x); // 离散化 x
		
		add.push_back({x, c});
	}
	for (int i = 1; i <= m; i++)
	{
		int l, r;
		cin >> l >> r;
		alls.push_back(l); // 离散化l
		alls.push_back(r); // 离散化r
		
		query.push_back({l, r}); // 记录操作
	}
	
	// 离散化过程
	sort(alls.begin(), alls.end());
	alls.erase(unique(alls.begin(), alls.end()), alls.end());
	
	for (auto t : add)
	{
		int x = find(t.first);
		a[x] += t.second;
	}
	
	// 前缀和
	for (int i = 1; i <= (int)alls.size(); i++) s[i] = s[i - 1] + a[i];
	
	// 查询
	for (auto t : query)
	{
		int l = find(t.first), r = find(t.second);
		cout << s[r] - s[l - 1] << endl;
	}
	
	return 0;
}

// 哈希表
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
vector<int> alls; // 存离散化之后的值
vector<PII> add, query;

unordered_map<int, int> mp; // 哈希表

int a[N], s[N];
int n, m;


int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		int x, c;
		cin >> x >> c;
		alls.push_back(x); // 离散化 x
		
		add.push_back({x, c});
	}
	for (int i = 1; i <= m; i++)
	{
		int l, r;
		cin >> l >> r;
		alls.push_back(l); // 离散化l
		alls.push_back(r); // 离散化r
		
		query.push_back({l, r}); // 记录操作
	}
	
	// 离散化过程
	sort(alls.begin(), alls.end());
	alls.erase(unique(alls.begin(), alls.end()), alls.end());
	
	for (int i = 0; i <= (int)alls.size() - 1; i++) mp[alls[i]] = i + 1; // 映射到下标从1开始
	
	for (auto t : add)
	{
		int x = mp[t.first];
		a[x] += t.second;
	}
	
	// 前缀和
	for (int i = 1; i <= (int)alls.size(); i++) s[i] = s[i - 1] + a[i];
	
	// 查询
	for (auto t : query)
	{
		int l = mp[t.first], r = mp[t.second];
		cout << s[r] - s[l - 1] << endl;
	}
	
	return 0;
}