整数离散化

• 去重模板

cpp sort(v.begin(), v.end()); // 先排序 // unique函数将两个迭代器中间的元素去重，然后返回去重之后的数组的下一个元素。这样我们再erase一下可以将重复的元素去除。 v.erase(unique(v.begin(), v.end()), v.end);

• 因为区间虽然大，但是数字很稀疏。我们先把需要用到的数字放到一个 vector 里面，然后去重。把每一个点映射到一个更小的数组的一个点上。这样可以减少空间的使用以及降低事件复杂度。

• 这里的代码为了求前缀和更方便，把在 find 函数中把返回的下标都加上了1。其实不加问题应该也不大

```cpp
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]

using namespace std;

const int N = 300000 + 10;

typedef pair[HTML_REMOVED] pii;
typedef vector[HTML_REMOVED] vi;
typedef vector[HTML_REMOVED] vpi;
#define xx first
#define yy second

int n, m;
vpi add, query;
vi v;
int s[N];

int find(int x)
{
int l = 0, r = v.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (v[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1; // 下标要从1开始，因此这里把每个下标都加上1
}

int main()
{
cin >> n >> m;
for (int i = 0; i < n; i )
{
int x, c;
cin >> x >> c;
v.push_back(x);
add.push_back({x, c});
}
for (int i = 0; i < m; i )
{
int l, r;
cin >> l >> r;
v.push_back(l), v.push_back(r);
query.push_back({l, r});
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 0; i < n; i )
{
int pos = find(add[i].xx);
s[pos] += add[i].yy;
}
for (int i = 1; i <= v.size(); i ) s[i] += s[i - 1];
for (int i = 0; i < m; i ++ )
{
int l = find(query[i].xx);
int r = find(query[i].yy);
cout << s[r] - s[l - 1] << endl;
}

  return 0;

}
```