【基础】离散化

本文主要是介绍【基础】离散化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 模板

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
}

---

 

AcWing 802. 区间和 - AcWing

假定有一个无限长的数轴，数轴上每个坐标上的数都是 00。

现在，我们首先进行 nn 次操作，每次操作将某一位置 xx 上的数加 cc。

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

输入格式

第一行包含两个整数 nn 和 mm。

接下来 nn 行，每行包含两个整数 xx 和 cc。

再接下来 mm 行，每行包含两个整数 ll 和 rr。

输出格式

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

数据范围

−109≤x≤109−109≤x≤109,
1≤n,m≤1051≤n,m≤105,
−109≤l≤r≤109−109≤l≤r≤109,
−10000≤c≤10000−10000≤c≤10000

输入样例：

Copy

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

输出样例：

Copy

8
0
5

难度：简单

时/空限制：2s / 64MB

总通过数：98846

总尝试数：172775

来源： 模板题

算法标签

---

挑战模式

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#define pii pair<int,int>
int n,m;
vector<int> alls;
vector<pii> add;
vector<pii> query;
const int N=300010;
int a[N],s[N];//总体而言，是把操作存进去，统计了要看哪一些，载重新取出来int findd(int x){int l=0,r=alls.size()-1;//l,r是可以取到的while(l<r){int mid=(l+r)>>1;if(alls[mid]>=x)r=mid;else l=mid+1;}return r+1;//新的从1存
}int main(){cin>>n>>m;for(int i=1;i<=n;i++){int x,c;cin>>x>>c;add.push_back({x,c});alls.push_back(x);}for(int i=1;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=findd(item.first);a[x]+=item.second;}for(int i=1;i<=alls.size();i++)s[i]=s[i-1]+a[i];for(auto item:query){int l=findd(item.first);int r=findd(item.second);cout<<s[r]-s[l-1]<<endl;}}

这篇关于【基础】离散化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---