区间和 离散化模板

ACWING 802 区间和

#include <bits/stdc++.h>

using namespace std;

const int N = 300010;
using PII = pair<int, int>;

int a[N];     //离散化后坐标点上的值
int s[N];     //离散化后坐标点上的前缀和
vector<PII>  add, query;
vector<int> all;    //储存离散化映射
int n, m;

int find(int x) {
   
    //从坐标映射到a[]和s[]中
    int l = 0, r = all.size() - 1;
    while (l <= r) {
   
        int mid = (l + r) >> 1;
        if (all[mid] == x) {
   
            return mid + 1; //a和s从1开始存放
        }
        else if (all[mid] < x) {
   
            l = mid + 1;
        }
        else {
   
            r = mid - 1;
        }
    }
    return -1;
}

int main() {
   
#ifndef ONLINE_JUDGE
    freopen("D:/VS CODE/C++/in.txt", "r", stdin);
    freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
   
        int x, c;
        scanf("%d %d", &x, &c);
        add.push_back({
   x, c});
        all.push_back(x);
    } 

    for (int i = 0; i < m; ++i) {
   
        int l, r;
        scanf("%d %d", &l, &r);
        query.push_back({
   l, r});
        all.push_back(l);
        all.push_back(r);
    }

    sort(all.begin(), all.end());   //将all进行排序
    all.erase(unique(all.begin(), all.end()), all.end());
    //使用unique函数对all容器相邻元素进行去重
    //unique返回值是去重后容器中最后一个元素的下一个位置

    int cnt = 0;
    for (auto item : add) {
   
        a[find(item.first)] += item.second;
        ++cnt;
    }

    for (int i = 1; i <= all.size(); ++i) {
   
        //求前缀和
        s[i] += s[i - 1] + a[i];
    }

    for (auto item : query) {
   
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }


    fclose(stdin);
    fclose(stdout);
    return 0;
}