acwing 802 区间和

//将离散的点集中起来，省空间，利用前缀和，省时间
#include
#include
#include
using namespace std;
typedef pair PII;
const int N = 3e5 + 10;
int n,m;
int a[N],s[N];
vector alls;
vector 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 l + 1;
    
}
int main(){
   cin >>n >>m;
   for(int i = 0;i < n; i ++)
   {
       int x,c;
       cin>>x >> c;
       add.push_back({x,c});
       alls.push_back(x);
   }
   for(int i = 0; i < m; i ++){
       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){
       a[find(item.first)] += item.second;
   }
   //预处理前缀和
   for(int i = 1; i < alls.size() + 1; i ++) s[i] = s[i - 1] + a[i];
   //处理询问
   for(auto item : query){
       int l = find (item.first), r = find (item.second);
    //int res = 0;
    //   for(int i = l; i <= r; i ++)//如果不用前缀和，直接暴力求解，时间复杂度是o(nm),n是区间长度，m是区间个数
    //   res += a[i];
    //   cout <