本人初学,做个总结,有错请指出。
理解:
举个例子:
-100000000000 100 100000 999999999 999999988888888
可以映射成 1 2 3 4 5.这样进行的操作就叫离散化。
离散化过程:
先排序,去重,然后二分找到这个数值的下标,这个数值离散化后的数就是这个下标。比如上面的例子,100 离散化后是2
用途:
对于数字值域很大,但是个数不太多的操作。
例如要在坐标范围为-1e9~1e9之间进行操作,给你一些坐标点,在这个点上加上一个值c,最后给出询问区间范围,求前缀和。
这里明显开不了数组,有负数,而且值很大。所以可以对坐标进行离散化,因为个数不多。
模板题
//首先对原数组排序, 去重, 离散化
//
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+9;
typedef pair<int,int> PII;
vector<PII> query, op;
vector<int> cor;
int a[N];
int find(int x)
{
int l = 0,r = cor.size()-1;
while(l<r)
{
int mid = (l+r)>>1;
if(cor[mid]>=x) r = mid;
else l = mid+1;
}
return r+1;
}
int main()
{
int n,m;
cin>>n>>m;
//输入操作,用option数组存储
for(int i=0;i<n;i++)
{
int x,c;
scanf("%d %d",&x,&c);
op.push_back({
x,c});
cor.push_back(x);
}
//输入m次询问的区间
for(int i=0;i<m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
query.push_back({
l,r});
cor.push_back(l);
cor.push_back(r);
}
sort(cor.begin(),cor.end());//对坐标进行排序
cor.erase(unique(cor.begin(),cor.end()),cor.end());//删除重复元素
//进行操作加c操作
for(int i=0;i<n;i++)
{
int x = find(op[i].first);//离散化后对应的坐标
a[x]+=op[i].second;
}
//求前缀和
for(int i=1;i<=(int)cor.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);
printf("%d\n",a[r]-a[l-1]);
}
return 0;
}