#include<iostream> #include<vector> #include<algorithm> using namespace std; typedef pair<int,int>PII2; vector<int>q; vector<PII2>PII,PII1; const int N=3e5+10; int el[N]; int vl[N]; int sum[N]; int main(){ int n,m; cin>>n>>m; while(n--) { int x,c; cin>>x>>c; PII.push_back({x,c}); q.push_back(x); } while(m--){ int l,r; cin>>l>>r; q.push_back(l); q.push_back(r); PII1.push_back({l,r}); } sort(q.begin(), q.end()); q.erase(unique(q.begin(), q.end()), q.end()); int k=0;//去掉重复元素 for(auto item : PII){ int x=item.first; int l=0,r=q.size()-1; while(l<r){ int mid=(l+r)/2; if(q[mid]>=x)r=mid; else l=mid+1; } vl[l+1]+=item.second; } for(int i=1;i<=q.size();i++){ sum[i]=sum[i-1]+vl[i]; } int l,r; for(auto item : PII1){ l=0,r=q.size()-1; while(l<r){ int mid=(l+r)/2; if(q[mid]>=item.first)r=mid; else l=mid+1; } int a=l+1; l=0,r=q.size()-1; while(l<r){ int mid=(l+r)/2; if(q[mid]>=item.second)r=mid; else l=mid+1; } int b=l+1; cout<<sum[b]-sum[a-1]<<endl; } return 0; }
标签:int,mid,back,item,while,push,区间,802,Acwing From: https://www.cnblogs.com/ljq20204136/p/16840019.html