【专题复习】离散化

前言

离散化思想可以理解为“只处理有效数据”的一种思想，对于问题的模型进行结构重建基本参考坐标是离散化代码实现的常见方法。对于数值范围巨大而实际有效点较少的问题可以采用离散化转化为更容易实现的问题求解。

说人话，离散化就是一个排名与值的映射，通过处理排名，让值在数组或循环中不出现，从而省空间或者时间。有些问题中，我们只需要关注排名，就可以离散化，比如：求逆序对。我们在只需要关注这个数在数组中的排名，用排名进入树状数组就行。

多应用于程序的优化而不是单独的算法，是一种思想。

例题

1. 校门外的树(加强版)

有 $L<=10^9，M<=100$

分析

这里直接开桶肯定就不行。所以直接对于区间离散化，然后每次枚举的时候就判断这个小区间是否被某个输入的区间完全涵盖，累加即可，注意在区间交界点有可能被多减一次，这样每减一次就要打上标记，碰到连续区间再加回来。

上代码

#include
#include
#include
using namespace std;

int n,m,l[110],r[110],a[210];
int ans,ff=-1;

int main()
{
	cin>>n>>m;
	ans=n+1;
	for(int i=1;i<=m;i++)
	{
		cin>>l[i]>>r[i];
		a[2*i-1]=l[i];
		a[2*i]=r[i];
	}
	sort(a+1,a+2*m+1);
	for(int i=1;i<=2*m-1;i++)
	{
		int len=a[i+1]-a[i]+1;
		for(int j=1;j<=m;j++)
		{
			if(l[j]<=a[i]&&r[j]>=a[i+1])
			{
				ans-=len;
				if(ff==a[i]) ans++;
				ff=a[i+1];
				break;
			}
		} 
	}
	cout<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

2. 矩形面积

分析

这道题看到坐标范围特别大，那就将横纵坐标分别离散化，排序后枚举每个横纵坐标围成的小区域，如果被某个输入的矩形覆盖的话就加入面积。其实就是上一题拓展成二维的。

上代码

#include
#include
#include
using namespace std;
int n;
long long x1[110],y1[110],x2[110],y2[110],x[210],y[210]; 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
		/*离散化：把具体的数存到下标为1~2n的数组当中*/
		x[i*2-1]=x1[i];
		x[i*2]=x2[i];
		y[i*2-1]=y1[i];
		y[i*2]=y2[i];
	}
	sort(x+1,x+2*n+1);//排序 
	sort(y+1,y+2*n+1);
	long long ans=0;
	for(int i=1;i<=2*n-1;i++)
	{
		for(int j=1;j<=2*n-1;j++)
		{
			long long s=(y[j+1]-y[j])*(x[i+1]-x[i]);
			for(int k=1;k<=n;k++)
			{
				if(x[i]>=x1[k]&&x[i+1]<=x2[k]&&y[j]>=y1[k]&&y[j+1]<=y2[k])
				/*如果有刚好涵盖ta的就证明这块面积需要被统计*/
				{
					ans+=s;
					break;//只能统计一次 
				}
			} 
		}
	}
	cout<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

变式

1. 幻灯片

分析

同样地，坐标范围巨大，直接二维离散化。
与例题2一样的，处理所有被覆盖的面积，但是要求出覆盖了几层（枚举的时候累加就行），然后开个桶记录颜色种类（是否被访问过）。

注意：如果两个区间刚好相邻（在一条线上），就会访问两次，所以要去重+循环时判定。

其实也就是模板+小处理。

上代码

#include
#include
#include
using namespace std;

int n,x1[110],x2[110],y1[110],y2[110],x[210],y[210],color[110];
int cnt[50010],ans;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x1[i]>>y1[i]>>x2[i]>>y2[i]>>color[i];
		x[2*i-1]=x1[i];
		x[2*i]=x2[i];
		y[2*i-1]=y1[i];
		y[2*i]=y2[i];
    }
	sort(x+1,x+2*n+1);
	sort(y+1,y+2*n+1);
	int xx=unique(x+1,x+2*n+1)-x-1;
	int yy=unique(y+1,y+2*n+1)-y-1;
	for(int i=1;i<=xx-1;i++)
	{
		for(int j=1;j<=yy-1;j++)
		{
			int tot=0;
			if(x[i]==x[i+1]||y[i]==y[i+1]) continue;
			for(int k=1;k<=n;k++)
			{
				if(x1[k]<=x[i]&&x2[k]>=x[i+1]&&y1[k]<=y[j]&&y2[k]>=y[j+1])
				{
					tot+=color[k];
				}
			}
			if(!cnt[tot]&&tot) ans++;
			cnt[tot]=1;
		}
	}
	cout<<ans;
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

2. Shaping Regions

分析

后面提示信息那里说了一堆废话，其实一点用都没有，就不放上来了。

同样的做二维离散化，暴力枚举围成的每个小矩形区域，判断是否有输入的矩形涵盖ta，统计答案。

但是这里要求面积，关键在于怎么统计答案。开个桶记录每种颜色的面积，因为最后加进去的一定尽可能在上面，所以对于每个枚举的小矩形区域，只需要从后往前找到涵盖ta的矩形，就是这一块的最终颜色，算面积方法显然。

上代码

#include
#include
#include
using namespace std;

int a,b,n,x1[1010],y1[1010],x2[1010],y2[1010],x[2010],y[2010],color[1010];
int ans[2510];

int main()
{
	cin>>a>>b>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x1[i]>>y1[i]>>x2[i]>>y2[i]>>color[i];
		x[2*i-1]=x1[i];
		x[2*i]=x2[i];
		y[2*i-1]=y1[i];
		y[2*i]=y2[i];
	}
	sort(x+1,x+2*n+1);
	sort(y+1,y+2*n+1);
	for(int i=1;i<=2*n-1;i++)
	{
		for(int j=1;j<=2*n-1;j++)
		{
			int s=(x[i+1]-x[i])*(y[j+1]-y[j]);
			for(int k=n;k>=1;k--)
			{
				if(x1[k]<=x[i]&&x2[k]>=x[i+1]&&y1[k]<=y[j]&&y2[k]>=y[j+1])
				{
					ans[color[k]]+=s;
					break;
				}
			}
		}
	}
	ans[1]=a*b;
	for(int i=2;i<=2500;i++) ans[1]-=ans[i];
	for(int i=1;i<=2500;i++)
	{
		if(ans[i]) cout<<i<<' '<<ans[i]<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44