离散化（acwing）

适用：值域跨度很大，但所用的很稀疏
//一个无限长坐标轴 在某个位置加上一个数（n次） 询问从l到r之间共加了多少（询问m次） 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=3e5+10;
int a[N],s[N],n,m;
vector<int> cun;    //cun 存所有加上数的坐标 以及 需要查询的坐标 
typedef pair<int,int> PII;           //pair比较方便 （x处，加上s）（查询l，查询r）都是两两一对 
vector<PII> add,zhao;         //add存所有加数的坐标以及加的数  zhao存所有要查询的坐标 
int find(int x)      //死模板，二分查找（离散化必备） 
{
	int l=0,r=cun.size()-1;
	while(l<r)
	{
		int mid=l+r>>1;
		if(cun[mid]>=x)
		r=mid;
		else
		l=mid+1;
	}
	return r+1;     //因为映射到a数组中是从1开始 所以现在要加1（cun里是从0开始存的） 
}
int main(void)
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		int xi,x;
		cin>>xi>>x;
		add.push_back({xi,x});   //存进add中 
		cun.push_back(xi);   //坐标存进cun中 
	}
	for(int i=0;i<m;i++)
	{
		int l,r;
		cin>>l>>r;
		zhao.push_back({l,r});   //存进zhao中 
		cun.push_back(l);   //坐标都存进cun中 
		cun.push_back(r);
	}
    //去重 
	sort(cun.begin(),cun.end());   //先排序 
	cun.erase(unique(cun.begin(),cun.end()),cun.end());  //背过 
	for(auto i:add)
	{
		int x=find(i.first);    //找出add里第一个元素，就是加数的坐标排第几个 
		a[x]+=i.second;         //在第x个位置加上add里第二个元素，也就是要加的数 
	}
	for(int i=1;i<=cun.size();i++)
	s[i]=s[i-1]+a[i];     //前缀和 
	for(auto i:zhao)
	{
		int l=find(i.first);
		int r=find(i.second);
		cout<<s[r]-s[l-1]<<endl;
	 } 
	return 0;
}