1, Meaning of discretization:

For array a [] = {1,31002000500000,...}, Map them one by one to subscripts 0,1,2,3,4 This process is called discretization

be careful:

1. There may be duplicate elements in a [], which need to be de duplicated
2. How to calculate the value of x after discretization: dichotomy

2, Discrete process

Usage of vector::erase(): delete an element from the vector. The parameter is the position of the element to be deleted

Usage of vector::erase(first,last): delete elements (excluding last) in the range of [first,last) from vector

Usage of vector::unique(first,last): within the range of [first, last] (excluding last), judge whether the current element is equal to the previous element, and move the non repeated elements to the front (not the repeated elements to the back); the containers to be de duplicated must be sorted and ordered

Usage of vector::unique(first,last,pred): the parameter pred can be used to determine the way of repetition

vector<int> a; //Store all values to be discretized
sort(a.begin(), a.end()); //sort
a.erase(unique(a.begin(), a.end()), a.end());   //duplicate removal

// Find the discretized value corresponding to x
int find(int x) // Find the first position greater than or equal to x
{
    int l = 0, r = a.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) 
            r = mid;
        else 
            l = mid + 1;
    }
    return r + 1; // Map to 1, 2 n; If r is returned, it is mapped to 0,1,2 n
}

3, Matching exercises

AcWing802https://www.acwing.com/problem/content/804/

std::pair(class1,class2) name usage: when creating a pair object, two type names must be provided, and the types of the two corresponding type names do not have to be the same; Pair is to combine two data into a group of data. When such requirements are required, pair can be used; Another application is to select pair when a function needs to return two data; The implementation of pair is a structure. The two main member variables are first and second. These two values can be accessed by two public functions of pair, first and second

C + + feature: range based for loop (datatype rangevariable: array)

• dataType: is the data type of the range variable. It must be the same as the data type of the array element, or the type that the array element can automatically convert.
• rangeVariable: is the name of the range variable. This variable will receive the values of different array elements during the loop iteration. During the first loop iteration, it receives the value of the first element; During the second loop iteration, it receives the value of the second element; and so on.
• Array: is the name of the array to be processed by the loop. The loop iterates once for each element in the array.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls;
vector<PII> 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) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }

    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    // duplicate removal
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    // Process insert
    for (auto item : add)
    {
        int x = find(item.first);
        a[x] += item.second;
    }
    // Preprocessing prefix and
    for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];
    // Handling inquiries
    for (auto item : query)
    {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}
//Link: https://www.acwing.com/activity/content/code/content/40105/