本文主要是介绍使合理化的有效trick，让二分搜索到的每一个点都是合理的，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
假定有一个无限长的数轴，数轴上每个坐标上的数都是 00。
现在，我们首先进行 nn 次操作，每次操作将某一位置 xx 上的数加 cc。
接下来，进行 mm 次询问，每个询问包含两个整数 ll 和 rr，你需要求出在区间 [l,r][l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 nn 和 mm。
接下来 nn 行，每行包含两个整数 xx 和 cc。
再接下来 mm 行，每行包含两个整数 ll 和 rr。
输出格式
共 mm 行，每行输出一个询问中所求的区间内数字和。
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+50;
int loc[N];
int add[N];
vector<int>map_loc;
int n,m;
int v[N];
int s[N];
pair<int,int>l_r[N];
int get_first(int x)
{int l=0,r=map_loc.size()-1;while (l<r){int mid=l+r>>1;if(map_loc[mid]>=x){r=mid;}else{l=mid+1;}}return r+1;
}int get_last(int x)
{int l=0,r=map_loc.size()-1;while (l<r){int mid=l+r+1>>1;if(map_loc[mid]<=x){l=mid;}else{r=mid-1;}}return r+1;
}
int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%d%d",&loc[i],&add[i]);map_loc.push_back(loc[i]);}for(int i=0;i<m;i++){scanf("%d%d",&l_r[i].first,&l_r[i].second);map_loc.push_back(l_r[i].first);//合理化，一定能二分搜索到map_loc.push_back(l_r[i].second);}sort(map_loc.begin(),map_loc.end());map_loc.erase(unique(map_loc.begin(),map_loc.end()),map_loc.end());for(int i=0;i<n;i++){int pos=get_first(loc[i]);v[pos]+=add[i];}for(int i=1;i<N;i++){s[i]=s[i-1]+v[i];}for(int i=0;i<m;i++){int pos1=get_first(l_r[i].first);int pos2=get_first(l_r[i].second);printf("%d\n",s[pos2]-s[pos1-1]);}return 0;
}这篇关于使合理化的有效trick，让二分搜索到的每一个点都是合理的的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
