一. 题目

二. 思路

• 本题思路：离散化+前缀和, 因为最多只有3e5(x+l+r)不同的数, 所以可以把-1e9到1e9离散化到1~3e5这个区间内。详见代码

三. 代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N=3e5+10, INF=2e9;
using PII=pair<int, int>;

int n, m;
int a[N];
vector<PII> add, q;//添加操作和q

class Discretization
{
public:
    vector<int> lsh;

public:
    Discretization()
    {
        initIO();
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    void init()//排序去重
    {
        sort(lsh.begin(), lsh.end());
        lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
    }

    int getIdx(int x)
    {//迭代器相减
        return lower_bound(lsh.begin(), lsh.end(), x)-lsh.begin();
    }
}d;

class PrefixAnd
{
public:
    int s[N];

public:
    void initS(int n)
    {
        for(int i=1;i<n;++i)
            s[i]+=s[i-1];
    }

    int getPa(int l, int r)
    {
        return s[r]-s[l-1];
    }
}pa;

int main()
{
    cin>>n>>m;
    
    d.lsh.emplace_back(-INF);//让离散化后的下标从1开始
    for(int i=0;i<n;++i)
    {
        int x, v;
        cin>>x>>v;
        d.lsh.emplace_back(x);
        add.emplace_back(x, v);
    }

    for(int i=0;i<m;++i)
    {
        int l, r;
        cin>>l>>r;
        q.emplace_back(l, r);//哈希的是用到的值(前缀和是l-1, 差分是r+1)，
        d.lsh.emplace_back(l-1);//否则哈希完后求l-1的新值可能出错
        d.lsh.emplace_back(r);
    }
    d.init();//排序去重

    for(auto it:add)
    {
        int x=d.getIdx(it.first);
        pa.s[x]+=it.second;
    }
    pa.initS(d.lsh.size());//初始化前缀和

    for(auto it:q)
    {
        int l_1=d.getIdx(it.first-1);
        int r=d.getIdx(it.second);
        cout<<pa.getPa(l_1+1, r)<<endl;
    }
}