两点问题
1、all忘记去重
2、二分的数组范围想错了
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef pair<int,int> PLL;
const int N = 300010;
vector<PLL> add,query;
int s[N];
int n,m;
vector<int> all;
int find(int x){
int l=-1,r=all.size();//注意处理好数组范围
while(l+1<r){
int mid=l+r>>1;
if(all[mid]>x)r=mid;
else l=mid;
}
return r;
}
int main()
{
//将所有数整到一个集合里去进行排列
//all[]为全数
//add<int,int>为加数组
//query[]为查询数组
cin>>n>>m;
for(int i=0;i<n;i++){
int x,c;cin>>x>>c;
all.push_back(x);
add.push_back({x,c});
}
for(int i=0;i<m;i++){
int l,r;cin>>l>>r;
all.push_back(l);all.push_back(r);
query.push_back({l,r});
}
//无限长:整个离散化//map g为离散数组
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());//要注意去重
//计算前缀和//s[]为前缀和数组
for(auto t:add){
int x=find(t.first),c=t.second;
//找到对应下标,处理加操作
s[x]+=c;
}
for(int i=1;i<=all.size();i++)s[i]+=s[i-1];
//再进行查询
for(auto t:query){
int l=find(t.first),r=find(t.second);
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}