两种离散化方法分析

  当给定的下标范围很大，如1e9，而输入的数的个数较少，如1e5。如果不做离散化，直接用数组存储，就会MLE。因此离散化必不可少。

  离散化的核心思想： 用新的从1开始的下标来映射输入的原始下标(很大)，这样我们就只需要开比较小的数组。

  而离散化的方式一般可以分为两种。

1、输入不需要维护其先后顺序

  当题目输入不需要维护其先后顺序时，可以直接用 hash 存储，每一个输入下标对应一个新的下标，新的下标可以从1开始。这种情况比较简单。

unordered_map<int, int> h;
int m;
//映射函数，m是x对应的新的下标，从1开始
int get(int x){
	if(h.count(x) == 0) h[x] = ++m;    //注意这里要用.count()来判断，否则如果用h[x]来判断，x就会被放入h中
	return h[x];
}
//输入的a, b是1e9范围
for(int i = 0; i < n; i++){
	scanf("%d%d%d", &a, &b, &e);
	int x = get(a), y = get(b); 
	query[i] = {x, y, e};
}

练习题============《程序自动分析》

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

unordered_map<int, int> h;
int p[N];
int n;
int idx;

struct Query{
	int a, b, e;
}query[N];

int get(int x){
	if(h.count(x) == 0) h[x] = ++idx;
	return h[x];
}

int find(int x){
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}

int main(){
	int T;
	scanf("%d", &T);
	while(T -- ){
		scanf("%d", &n);
		h.clear(); 
		int a, b, e;
		idx = 0;
		for(int i = 0; i < n; i++){
			scanf("%d%d%d", &a, &b, &e);
			int x = get(a), y = get(b); 
			query[i] = {x, y, e};
		}
		
		for(int i = 1; i <= idx; i++) p[i] = i;
		
		for(int i = 0; i < n; i++){
			int a = query[i].a, b = query[i].b, e = query[i].e;
			if(e == 1) {
				int pa = find(a), pb = find(b);
				p[pa] = pb;
			}
		}
		
		bool has_conflict = false;
		//枚举询问看是否有冲突 
		for(int i = 0; i < n; i++){
			int a = query[i].a, b = query[i].b, e = query[i].e;
			if(e == 0){
				int pa = find(a), pb = find(b);
				if(pa == pb) {
					has_conflict = true;
					break;
				}
			}
		}
		if(has_conflict) puts("NO");
		else puts("YES");
	}
	
	return 0;
} 

2、输入需要维护顺序

  当输入需要维护顺序时，如代表的含义是区间范围，处理的方式为：

① 先将所有输入的下标当做值存起来

for(int i = 0; i < m; i++){
	int l, r;
	scanf("%d%d", &l, &r);
	alls.push_back(l), alls.push_back(r);
	query.push_back({l, r});
}

② sort排序

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

③ unique + erase 去重

alls.erase(unique(alls.begin(), alls.end()), alls.end());

④ 通过二分来找到某个输入下标离散化后的新下标

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开始
}

练习题============《区间和》

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

typedef pair<int, int> PII;

const int N = 300010;
int a[N], s[N];
vector<PII> add, query;
vector<int> alls;  //所有坐标 
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;
		else l = mid + 1;
	}
	return l + 1;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i++){
		int x, c;
		scanf("%d%d", &x, &c);
		alls.push_back(x);
		add.push_back({x, c}); 
	}
	for(int i = 0; i < m; i++){
		int l, r;
		scanf("%d%d", &l, &r);
		alls.push_back(l), alls.push_back(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 = t.first, c = t.second;
		a[find(x)] += c;
	}
	
	//计算前缀和
	for(int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i]; 
	
	for(auto& q : query){
		int l = find(q.first), r = find(q.second);
		printf("%d\n", s[r] - s[l - 1]);
	}
	
	return 0;
}