题目描述

可以参考下我的离散化思路。 首先我们可以很明确的是对于每一个 下标x，都会对应一个值v.
然后让我们求下标区间为[l, r]之间的所有 value 之和。
题目难就在于 下标x是非常离散的。如果直接用前缀和的思路，时间开销是 O(n) n为1e9. 超时

然后我们的思路是按照下标 x 值大小， 从小到大对应到一个数组 a[].
然后其值大小一个对应一个数组 b[].

其中 a， b的值是连续的，消除了离散化。
最终对于求区间 [l, r]时候，我们二分查找到位置. le, ri, 即可得到解。
时间福再度 O(1e6)

C++ 代码

using namespace std;
const int N=100010;
map[HTML_REMOVED] v;
int a[N], s[N];
int main(){
int n, m;
cin>>n>>m;
for(int i=0, x, c; i[HTML_REMOVED]>x>>c;
v[x] += c;
}
int k = 1;
for(auto &x:v){
a[k] = x.first;
s[k] = s[k-1]+x.second;
k++;
}
int l,r;
while(m–){
cin>>l>>r;
int le = lower_bound(a+1, a+k, l)-a;//二分查找 对应于 前缀和的左右边界
int ri = upper_bound(a+1, a+k, r)-a-1;
cout<<s[ri]-s[le-1]<<endl;
}
}