【刷题】基础算法——离散化：区间和

【刷题】基础算法——离散化：区间和

对x和查询的l、r进行离散化，对于离散化后的数据进行前缀和。

#include 
#include 
#include 
using namespace std;

int n, m;
int a[300005], s[300005];

vector> add;
vector> query;
vector axis;

int find(int x) {
    int l = 0, r = axis.size() - 1;
    while(l < r) {
        int mid = l + r >> 1;
        if (axis[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

int main() {
    scanf("%d%d", &n, &m);
    int x, c;
    for (int i = 1; i <= n; i ++ ) {
        scanf("%d%d", &x, &c);
        add.push_back({x, c});
        axis.push_back(x);
    }
    
    int l, r;
    for (int i = 1; i <= m; i ++ ) {
        scanf("%d%d", &l, &r);
        axis.push_back(l);
        axis.push_back(r);
        query.push_back({l, r});
    }
    sort(axis.begin(), axis.end());
    axis.erase(unique(axis.begin(), axis.end()), axis.end());
    
    for (auto item : add) {
        int x = find(item.first);
        a[x] += item.second;
    }
    
    for (int i = 1; i <= axis.size(); i ++ ) {
        s[i] += s[i - 1] + a[i];
    }
    
    for (auto q : query) {
        int l = find(q.first), r = find(q.second);
        printf("%dn", s[r] - s[l - 1]);
    }
    
    return 0;
}