离散化 + 前缀的使用问题

1. 什么是离散化，一句话 值域很大，但是数字个数很少，那么就将数字进行映射，从而通过映射后的数值可以直接访问元素
2. 离散化第二个特点，就是有两个数字，其中数字下标从0,1,2,3,4,5,6……一直向后

1、离散化之前的原数值需要保存

1. 数据排好序
2. 去重(原因在于映射的时候,同一个数值，同一个映射下标，重复了，所以去重)
3. 得到去重之后的数值，边排序，此时是vector最好，但是下标从0开始的

2、vector保存之前的大数值，那么肯定需要这些下标吗，所以再使用的时候需要找到该数字映射之后的位置

1. 因为后查询的数字，该数组如果要比较大小，也不知道映射之后应该处于哪个地方
2. 所以咋进行映射的时候,需要将 需要映射的数值， 提前映射好，所以本题目的数字大小是300000;
3. 找原数值，那么就找到映射之后的新坐标，查找方式一定是存在的，所以直接二分查找即可，或者是找数字相同的第一个元素

3、因为是求解前缀和，所以我们需要将下标从1开始进行保存

1. 方式一： 二分查找的时候坐标多加一个
2. 方式二： 下标仍然是0， 多一个移动位数的操作即可

4、本题因为要数值求和，是一个一对一的关系，所以用pair进行保存数值

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 300010;

typedef pair<int,int> pII;

vector<pII> add, query;
vector<int> alls;
int a[N], s[N]; //前缀和计算
int n, m;

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

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n;i ++)
    {
        int x, c;
        scanf("%d%d", &x, &c);
        //先记录好x ,c之间的映射关系
        add.push_back({x,c});
        //需要将对应的数值坐标记录好并排序后去重
        alls.push_back(x);
    }
    //开始m次询问
    while(m--)
    {
        int l, r;
        scanf("%d%d", &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());

    //保存好了坐标之后，需要保存映射之后的数值，下标是从0开始的
    for(int i = 0;i < add.size(); i ++)
    {
        // cout << "i : " << add[i].first << " " << add[i].second << endl;
        //该数值映射之后的坐标应该是多少
        int x = find(add[i].first);
        //前缀和计算的时候下标从1开始的
        a[x] += add[i].second;
    }
    //计算前缀和
    int len = alls.size();
    for(int i = len-1;i >= 0;i--)
        a[i + 1] = a[i];
    a[0] = 0;
    // for(int i = 1;i <= len ;i ++)
    //     cout << a[i] << " ";
    // cout << endl;
    for(int i = 1;i <= len ;i ++)
    {
        s[i] = s[i - 1] + a[i];
    }
    for(auto c:query)
    {
        // cout << c.first << " " <<c.second << endl;
        int x = find(c.first), y = find(c.second);
        x++, y++;
        // printf("x = %d, y = %d\n", x, y);
        cout << s[y] - s[x - 1] << endl;
    }
    return 0;
}