离散化

Trace

区间和

传送门：https://www.acwing.com/problem/content/804/

Problem

假定有一个无限长的数轴，数轴上每个坐标上的数都是 00。

现在，我们首先进行 nn 次操作，每次操作将某一位置 xx 上的数加 cc。

接下来，进行 mm 次询问，每个询问包含两个整数 ll 和 rr，你需要求出在区间 [l,r][l,r] 之间的所有数的和。

输入格式

第一行包含两个整数 nn 和 mm。

接下来 nn 行，每行包含两个整数 xx 和 cc。

再接下来 mm 行，每行包含两个整数 ll 和 rr。

输出格式

共 mm 行，每行输出一个询问中所求的区间内数字和。

数据范围

$-1e9≤x≤1e9$

$1≤n,m≤1e5$

$-1e9≤l≤r≤1e9$

$−10000≤c≤10000$

输入样例：

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例：

8
0
5

思路：

离散化基础模板题

$x$的范围非常大，数组开不出来，但是实际用到的点不多，可以将这些用到的点映射到较小的数组中（保序），就是离散化。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> PIR;

// 所有坐标的点的个数，add最大1e5个点，query最多1e5次，每次两个点
const int N=300000+10;

// 所有坐标的点的个数
vector<int> alls;

vector<PIR> query;
vector<PIR> add;

int n,m;

// 离散化后的原数组
int a[N];
// 离散化后的前缀和数组
int s[N];

// 二分找映射后的位置
int find(int x){
    int l=0,r=alls.size()-1;
    while(l<r){
        int mid=(l+r)>>1;
        if(alls[mid]>=x){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    // 使离散化后的原数组从1开始，方便求前缀和
    return l+1;
}

int main()
{
    cin>>n>>m;
    while(n--){
        int x,c;
        cin>>x>>c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    
    while(m--){
        int l,r;
        cin>>l>>r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    
    //保序离散化+去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    
    
    // add
    for(int i=0;i<add.size();i++){
        int x=add[i].first;
        int c=add[i].second;
        a[find(x)]+=c;
    }
    
    // 预处理前缀和
    for(int i=1;i<=alls.size();i++){
        s[i]=s[i-1]+a[i];
    }
    
    // query
    for(int i=0;i<query.size();i++){
        int l=query[i].first;
        int r=query[i].second;
        cout<<s[find(r)]-s[find(l)-1]<<endl;
    }
    return 0;
    
}