【杂论：离散化】

一 . 离散化是什么

离散化本质上可以看成是一种哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系。

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

用来离散化的可以是大整数、浮点数、字符串等等。

二 . STL实现离散化

 

三 . 一维离散化

---

例题：洛谷 P1496 火烧赤壁

题目描述

给定每个起火部分的起点和终点，请你求出燃烧位置的长度之和。

输入格式

第一行一个整数，表示起火的信息条数 n。
接下来 n 行，每行两个整数 a, b，表示一个着火位置的起点和终点。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1

3
-1 1
5 11
2 9

输出 #1

11

说明/提示

数据规模与约定

对于全部的测试点，保证 1≤n≤2×10^4，-2^{31} ≤a ≤b<2^{31}，且答案小于2^{31}。

---

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn=1e8+5;
int c[maxn],n,cnt=0;
struct node{
	int x,y;
}edge[maxn];

bool vis[maxn];
inline long long int read()
{
	long long int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void write(long long int x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

inline long long int find(long long int x) 
                //找到排序后数据在映射表内的位置
{
	for(long long int i=1;i<=cnt;++i)
	{
		if(c[i]==x) return i;
	}
	return 0;
}

int main()
{
	long long int sum=0;
	memset(vis,false,sizeof(vis));
	n=read();
	for(long long int i=1;i<=n;++i)
	{
		edge[i].x=read();
		c[++cnt]=edge[i].x;
		edge[i].y=read();
		c[++cnt]=edge[i].y;
	}
	sort(c+1,c+cnt+1); //数据排序

	for(long long int i=1;i<=n;++i)
	{
		int x=find(edge[i].x);
		int y=find(edge[i].y);
		for(long long int j=x;j<=y-1;++j)
		{
			vis[j]=true;  //以映射表的位置的下标进行判断
		}
	}
	for(long long int i=1;i<=cnt;++i)
	{
		if(vis[i]) //两者之间被标记就记录长度
		sum+=c[i+1]-c[i]; 
	}
	write(sum);
	return 0;
}

---

四 . 二维离散化

 通过题目提供的坐标等条件，将目标矩形分割成不同的单位矩形，根据题目要求，判断各个单位矩形是否满足题目要求。

---

例题：洛谷 P4122 [USACO17DEC]Blocked Billboard B

题目描述

在平面直角坐标系中，有两个矩形（保证不相交），然后给出第三个矩形，求这两个矩形没有被第三个矩形遮住的部分的面积。

输入格式

题目给出三个坐标，分别表示三个矩形的左下、右上坐标，数据范围为[-1000,1000]。

输出格式

输出前两个矩形没有被第三个矩形覆盖的面积大小。

输入输出样例

输入 #1

1 2 3 5
6 0 10 4
2 1 8 3

输出 #1

17

说明/提示

样例中，第一个矩形有 5 单位面积没有被覆盖，第二个矩形有 12 个单位面积没有被覆盖。

---

• 暴力模拟

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int maxn=2200;
int m[maxn][maxn],ans=0;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void write(int x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

int main()
{
	int lx1=read(),ly1=read(),rx1=read(),ry1=read();
	int lx2=read(),ly2=read(),rx2=read(),ry2=read();
	int lx3=read(),ly3=read(),rx3=read(),ry3=read();

	for(int i=lx1+1000;i<rx1+1000;++i) //循环内的序号要+1000
    //根据数据范围可知会出现负数的情况，通过所有数据向后移动使其变为正整数
	{
		for(int j=ly1+1000;j<ry1+1000;++j)
		{
			m[i][j]=1;
			ans++;
		}
	}
	for(int i=lx2+1000;i<rx2+1000;++i)
	{
		for(int j=ly2+1000;j<ry2+1000;++j)
		{
			m[i][j]=1;
			ans++;
		}
	}
	
	for(int i=lx3+1000;i<rx3+1000;++i)
	{
		for(int j=ly3+1000;j<ry3+1000;++j)
		{
			if(m[i][j]==1)
			ans--;
		}
	}
	write(ans);
	return 0;
}

• 二维离散化