SnowDawn'Home
0%

离散化

发表于 分类于

概念

在一个很大的范围内 ， 只有 很小的数据容量。

使用离散化，将这些数据 存储在从 1 开始的数组里 ， 再进行后续的处理。

处理方法

  • 将输入的 值存入动态数组 vector
  • 将所有的值排序
  • 储存进数组的值相当于坐标 ， 所以要进行去重的操作，方便后续的使用和处理。
  • 编写一个find（）函数，用于找到原数据对应的离散化之后的数据位置（动态数组中的位置）
  • 根据题目的逻辑进行相应的 操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
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, ...n
}

模板例题

[求区间和](802. 区间和 - AcWing题库)

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 xx 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l ,r] 之间的所有数的和。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;				//数据范围限制，可能有 1e5 个add ， 和 2e5 个坐标

int n, m;
int a[N], s[N];						//相应坐标的数据，和最后求和时使用的前缀和

vector<int> alls;					//存储所有数据
vector<PII> add, query;				//两个操作，使用pair<int,int>存储一次操作中的两个参数

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()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});		//存储add操作
        alls.push_back(x);  		//存储原数据
    }

    for (int i = 0; i < m; i++)		//存储query操作
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});

        alls.push_back(l);			//存储询问的位置
        alls.push_back(r);
    }

    sort(alls.begin(), alls.end());	//排序和去重操作
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    for (auto item : add)			//处理add插入操作
    {
        int x = find(item.first);	//获取原数据离散化的坐标
        a[x] += item.second;		//修改相应坐标上的值
    }

    for (int i = 1; i <= alls.size(); i++)
        s[i] = s[i - 1] + a[i];		//处理前缀和
	
    for (auto item : query)			//处理query询问操作
    {
        int l, r;
        l = find(item.first), r = find(item.second);//获取离散化后坐标
        cout << s[r] - s[l - 1] << endl;			//利用前缀和求值输出
    }

    return 0;
}