算法学习

离散化+前缀和

#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