离散化介绍

算法模板

离散化题目模板

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
}

模板题

区间和

原题链接

https://www.acwing.com/problem/content/804/

题目

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

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

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

输入格式
第一行包含两个整数 n
和 m
。

接下来 n
行，每行包含两个整数 x
和 c
。

再接下来 m
行，每行包含两个整数 l
和 r
。

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

数据范围
−109≤x≤109
,
1≤n,m≤105
,
−109≤l≤r≤109
,
−10000≤c≤10000
输入样例：

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例：

8
0
5

题解

思路

进行 n次操作，每次操作将某一位置 x上的数加 c
m次询问，每个询问包含两个整数 l和 r
因此会涉及到n+2m个下标，而1≤n,m≤10^5,所以N开3e5+10
会用到的下标都会被保存到alls数组，这样就可以把这些数对应的下标离散化映射到自然数1,2,3,…下标

使用二分查找函数find（x）（x为原来的下标）即可查找到映射后在alls数组中对应的下标
然后使用前缀和处理来解决查询问题

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;const int N = 3e5 + 10;typedef pair<int,int> PII;int a[N],s[N]; //s[i]为a[i]的前缀和数组vector<int> alls; //存的是原下标！ 
vector<PII> add,query;
int n,m;
//二分查找 
int find(int x){ //查找x对应在alls数组中的下标 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表示从1开始映射，不+1表示从0开始映射 
}
int main(){cin>>n>>m;for(int i=0;i<n;i++){int x,c;cin>>x>>c;add.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(auto item : add){int x = find(item.first); //x即为原下标在alls数组中对应的下标。也即为离散化后映射的下标(1,2,3,...) a[x]+=item.second;} // 预处理前缀和for(int i=1;i<=alls.size();i++){s[i] = s[i-1]+a[i];} // 处理询问for(int i=0;i<m;i++){int l = find(query[i].first);int r = find(query[i].second);cout<<s[r] - s[l-1]<<endl;}
} 

unique原理补充介绍