算法1

使用map $O(N logN)$

y总的算法中使用了多个数组来进行映射、记录、排序等操作，这些操作都可以通过一个关联容器map来完成；

时间复杂度 $O(N logN)$

• map是一个排序关联容器，它的实现是基于红黑树的；
• 对map来说每一个插入操作和读取操作都是O(logN)的；
• 所以对于N个操作，它的插入(n+2m)及读取(2m)都是O(NlogN)级数；

C++ 代码

#include<iostream>
#include<vector>
#include<map>
using namespace std;

map<int, int> mp;                  //使用map存储每个x和l,r，并且记录他们的值，再转化为前缀和；
vector<pair<int, int> > query;     //记录查询操作；

int main()
{
    std::ios::sync_with_stdio(false);     //用于给cin提速；

    int n, m;
    cin>>n>>m;
    for(int i = 0; i < n; ++i){
        int x, c;
        cin>>x>>c;
        mp[x] += c;                    //若map中没有该元素则插入，若有则加上值c，同时覆盖了排序、去重操作
    }
    for(int i = 0; i < m; ++i){
        int l, r;
        cin>>l>>r;
        mp[l] += 0;
        mp[r] += 0;
        query.push_back({l, r});       //记录查询操作；
    }
    mp[-1e9-1] = 0;                    //相当于前缀和数组的s[0]，防止第一个操作出错；

    //前缀和处理
    for(auto it1 = mp.begin(), it2 = mp.begin(); it1 != mp.end(); ++it2)
        {
            ++it1;                     //此时it1类似s[i]与a[i]，it2落后一步，类似s[i-1]
            it1->second += it2->second;
        }
    //查询操作
    for(auto c : query){
        int l = c.first, r = c.second;
        auto it = mp.find(l);
        --it;
        cout<<mp[r] - it->second<<endl;   //s[r]-s[l-1]
    }
    return 0;
}

算法2

离散映射 $O(nlogn)$

• 离散化的目的是建立一个从某个集合到另一个集合的映射，其中这两个集合中的元素一定都是一一对应的，一般用于特别稀疏的数组或矩阵的存储(如本题)；
• 在本题中，使用数组alls建立了alls的下标和数轴上的点x的映射，即每一个点的坐标都对应了alls的一个下标，在前缀和数组s[N]中也是使用的和alls相同的下标，保证了s[N]中的元素和数轴上的点也是一一对应的关系；
• 对于保存pair类型的vector不能使用emplace_back()而只能使用push_back()的问题，目前认为是push_back将{l,r}进行了拷贝传给pair构造函数进行构造，而emplace_back直接在内存中进行了构造，将花括号中的内容定义为初始化列表；
• 以后弄清楚了我再来替换掉这一个条目，也欢迎各位大佬为我解惑；

时间复杂度 $O(nlogn)$

• 在建立alls数组时是线性时间复杂度O(N) N = n+2m；
• 对alls数组的排序sort O(NlogN);
• 对每个添加操作是常数级，所有添加操作加起来就是O(n);
• 前缀和化O(N);
• 对每个查询操作，都是O(logN)，所有查询操作加起来是O(mlogN);
• 综上所述，时间复杂度是O(NlogN)级别；

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 3e5+10;

int s[N];                               //保存每个数的值，后面会前缀和化；
vector<int> alls;                       //保存所有出现的点(包括插入和查询)，并建立下标和点坐标之间的映射；
vector<pair<int, int> > 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) l = mid + 1;
        else r = mid;
    }
    return r + 1;
}                                       //此查找是从点坐标到数组下标的一个转换；

int main()
{
    std::ios::sync_with_stdio(false);

    int n, m;
    cin>>n>>m;
    for(int i = 0; i < n; ++i){
        int x, c;
        cin>>x>>c;
        add.push_back({x, c});          //不能使用emplace_back()，会报错，但是push_back()可以
        alls.emplace_back(x);
    }
    for(int i = 0; i < m; ++i){
        int l, r;
        cin>>l>>r;
        query.push_back({l, r});
        alls.emplace_back(l);
        alls.emplace_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);
        s[x] += item.second;
    }
    //前缀和化
    for(int i = 1; i <= alls.size(); ++i) s[i] += s[i-1];
    //查询及输出
    for(auto item : query){
        int l = find(item.first);
        int r = find(item.second);
        cout<<s[r] - s[l-1]<<endl;
    }
    return 0;
}