题目描述
一个超级大的数轴上在某些点上加值,然后询问一个指定区间内的数值和。
算法
(离散化+二分) $O(nlogn)$
先将n组值有序离散至b数组中,然后求前缀和,在查询时,根据指定的区间左右端点去找在离散数组中的位置。然后通过前缀和数组相应数值相减即可。
本代码采用C++书写,比较原始,没有使用yxc大佬的相关迭代器,希望能让大家能看懂。
C++ 代码
//数轴太大,不方便开数组,因此先离散化存数据,然后二分找这个数的位置加值。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 6;
int x,c,n,m,k;
pair<int ,int>a[MAXN],b[MAXN];
long long sum[MAXN];
//精确查找是否存在该值。
int find(int x){
int left = 1,right = k;
while(left <= right){
int mid = (left + right) / 2;
if(b[mid].first == x) return mid;
else if(b[mid].first > x) right = mid-1;
else left = mid+1;
}
return 0;
}
bool cmp(pair<int ,int>x,pair<int,int>y){
if(x.first < y.first)return true;
else return false;
}
//二分查找满足条件的最小,采用左开右闭的方式。
int findsmall(int x){
int left = 0,right = k;
while(left+1 <right){
int mid = (left + right) / 2;
if(b[mid].first >= x) right = mid;
else left = mid;
}
if(b[right].first < x) return 0;
return right;
}
//二分查找满足条件的最大,采用左闭右开的方式
int findbig(int x){
int left = 1,right = k+ 1;
while(left+1 < right){
int mid = (left + right) / 2;
if(b[mid].first <= x) left = mid;
else right = mid;
}
if(b[left].first > x) return 0;
return left;
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i<= n ; i++){
scanf("%d%d",&x,&c);
a[i] = make_pair(x,c);
}
sort(a+1,a+1+n,cmp);
//离散化存至b数组中
for(int i = 1;i<= n; i++){
int pos = find(a[i].first);
if(pos == 0) b[++k] = a[i];
else b[pos].second += a[i].second;
}
//计算前缀和
for(int i = 1;i<= k; i++){
sum[i] = sum[i-1] + b[i].second;
}
//在离散数组中二分查找左边界和右边界,注意找不到的情况特判。
for(int i = 1;i<= m; i++){
int left,right;
scanf("%d%d",&left,&right);
int l = findsmall(left);
int r = findbig(right);
if(l == 0 ||r == 0) printf("0\n");
else{
printf("%lld\n",sum[r]-sum[l-1]);
}
}
return 0;
}