AcWing 802.区间和

题目链接：https://www.acwing.com/problem/content/804/

好像理解了，但又没完全理解....写个题解再好好理解一下。

百度说：离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

简单来说就是通过映射关系，将大范围里面很少的数据进行小范围存储，压缩了使用空间。

离散化常用的一般步骤：

1、对数据进行排序

2、对数据进行去重

3、离散化数据处理

我将本题分为这几步：

1、读入所有操作数据

2、离散化数据。将 n 次操作的坐标，m 次查询的 [l, r] 进行离散化

3、求离散化后数据前缀和

4、将 m 次查询的区间和输出。注意 l 和 r 都需要对应到离散化数据

find 函数的功能：输入映射前的位置 x ，返回映射后的位置+1。（+1的目的是为了求区间和时少一步下表为0的判断）

alls[N] 为什么要开 3e5+10？因为最多可以执行 n 次插入操作，m 次询问操作，而每次询问操作中会包含两个坐标。所以说虽然题目中说数轴是无限长，但离散化的数组只需要开 3e5+10 就够了。

关于为什么要去重，引用一个大佬的题解中的图：

然后分析一下样例：

放AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 3e5+10;//n次查询和m次询问相关数据量的上届
 4 int n, m;
 5 int a[N];//存储坐标插入的值
 6 int s[N];//存储a的前缀和
 7 vector<int> alls;//存储（所有与操作有关的）下标
 8 vector<pair<int,int> > add, query;//存储插入和询问操作的数据
 9 
10 int find(int x)
11 {//返回的是输入的坐标的离散化下标+1
12     int l = 0, r = alls.size() - 1;
13     while (l < r)
14     {
15         int mid = l + r >> 1;
16         if (alls[mid] >= x) r=mid;
17         else l = mid + 1;
18     }
19     return r + 1;
20 }
21 
22 int main()
23 {
24     cin >> n >> m;
25     for(int i=1; i<=n; i++)
26     {
27         int x, c;
28         cin >> x >> c;
29         add.push_back({x, c});
30         alls.push_back(x);//把x加到待离散化的数组中
31     }
32     for(int i=1; i<=m; i++)
33     {
34         int l, r;
35         cin >> l >> r;
36         query.push_back({l, r});
37         alls.push_back(l);//把l加到待离散化的数组中
38         alls.push_back(r);//同
39     }
40 
41     //排序+去重
42     sort(alls.begin(),alls.end());
43     alls.erase(unique(alls.begin(),alls.end()),alls.end());
44 
45     //执行前n次的插入操作
46     for(auto item : add)
47     {
48         int x = find(item.first);
49         a[x] += item.second;//在离散化之后的位置上加上要加的数
50     }
51 
52     //预处理前缀和
53     for(int i=1; i<=alls.size(); i++)
54         s[i] = s[i-1] + a[i];
55 
56     //处理后m次询问操作
57     for(auto item:query)
58     {
59         int l = find(item.first);//映射后的位置
60         int r = find(item.second);
61         cout << s[r]-s[l-1] << endl;
62     }
63     return 0;
64 }