算法学习
离散化+前缀和
#include
#include
#include
using namespace std;
const int N=300010;
int a[N],s[N];
typedef pair PII;
vectoralls;
vectoradd,query;
int find(int x){
int l=0,r=alls.size()-1;
while(l>1;
if(alls[mid]>=x) r=mid;
else l=mid+1;
}
return r+1;
}
int n,m;
int main(){
cin>>n>>m;
for(int i=0;i>x>>c;
alls.push_back(x);
add.push_back({x,c});
}
while(m--){
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=find(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=find(item.first);
int r=find(item.second);
cout<::iterator unique(vector &a){
//双指针用法
for(int i=0,j=0;i
原文:https://www.cnblogs.com/SCPC-QACY/p/15310120.html