离散化

离散化

离散化就是把大范围(值域很大)内稀疏的坐标映射到小范围内稠密的坐标,和数学没有关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
// return r; // 映射到0,1,...n-1
// 这里的n指的是总数据个数
}


问题

假定有一个无限长的数轴,数轴上每个坐标上的数都是0。
现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。
接下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。

输入格式

第一行包含两个整数n和m。
接下来 n 行,每行包含两个整数x和c。
再接下里 m 行,每行包含两个整数l和r。输入格式:

输出格式

共m行,每行输出一个询问中所求的区间内数字和。

数据范围

−10^9<=x<=10^9

1<=n,m<=10^5

−10^9<=l<=r<=10^9

−10000<=c<=10000

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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 3e5 + 10; // 因为修改会涉及到n个坐标,查询会涉及到2*m个坐标,最坏情况是这n+2*m个坐标全都不相等,那么映射后需要的空间最大也就3e5,+10减少边界问题

int n, m;
int a[N];
vector<pair<int, int>> adds, query;// 因为我们需要知道哪些坐标需要离散化,所以修改和查询操作需要先进行保存,不能直接处理了
vector<int> alls; // 保存需要进行离散化的坐标

// 通过二分巧妙实现将稀疏的数据映射到稠密的下标从而实现离散化
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 r + 1; // 将坐标映射到[1, alls.size()],而二分找到的结果是数组下标,应该是[0, alls.size() - 1]
}
int main()
{
cin >> n >> m;

// 读入修改操作
for (int i = 0; i < n; ++ i)
{
int x, c;
cin >> x >> c;
adds.push_back({x, c});
alls.push_back(x);
}

// 读入查询操作
for (int i = 0; i < m; ++ i)
{
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 (int i = 0; i < n; ++ i)
{
int x = find(adds[i].first);
a[x] += adds[i].second;
}

// 准备前缀和数组
for (int i = 1; i <= alls.size(); ++ i) a[i] += a[i - 1];

// 进行查询操作
for (int i = 0; i < m; ++ i)
{
int l = find(query[i].first), r = find(query[i].second);
cout << a[r] - a[l - 1] << endl;
}
return 0;
}