算法学习

离散化+前缀和

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=300010;
int a[N],s[N];
typedef pair<int,int> PII;
vector<int>alls;
vector<PII>add,query;
int find(int x){
    int l=0,r=alls.size()-1;
    while(l<r){
        int mid=l+r>>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<n;i++){
          int x,c;
          cin>>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<<s[r]-s[l-1]<<endl;    
      }
}

vector<int>::iterator unique(vector<int> &a){
   //双指针用法
   for(int i=0,j=0;i<a.size();i++)
   if(!i||a[i]!=a[i-1)//check判定条件
   {
      a[j]=a[i];
        j++;
   }
   return a.begin()+j;
}

算法学习

原文：https://www.cnblogs.com/SCPC-QACY/p/15310120.html