acwing 802. Interval sum (discretization)

Suppose there is an infinite number axis , The number on each coordinate on the number axis is 0.

Now? , Let's start with n operations , Each operation will a certain position x Add... To the number on c.

Next , Conduct m Time to ask , Each query contains two integers l and r, You need to find the interval [l,r] The sum of all numbers between .

Input format
The first line contains two integers n and m.
Next n That's ok , Each line contains two integers x and c.
Next m That's ok , Each line contains two integers l and r.

Output format
common m That's ok , Each line outputs a number in the interval and .

Data range
−10⁹≤x≤10⁹,
1≤n,m≤10⁵,
−10⁹≤l≤r≤10⁹,
−10000≤c≤10000
sample input ：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
sample output ：
8
0
5

Topic characteristics ：
Great value , The number is small .（ It's impossible to open one 1e9 Array of ）
Here we need to map to a small interval .

Specific mapping ideas ：

Problems encountered ：

1. a There may be repeating elements in （ duplicate removal ）
2. How to figure out x Discrete values （ because a It's order , Here we use two points to find ）

Sort plus duplicate code templates

vector<int> alls   //  Store all values to be discretized 
sort(alls.begin(), alls.end()); //  Array to sort 
alls.erase(unique(alls.begin(), alls.end()), alls.end());  //  Remove the repeating elements 

【 notes 】： unique（） The function is to put all the repeating elements in a later interval , Then return to the starting position of the interval . So to remove the repeating elements, just erase the next section .

Two points search x Corresponding discretized value

int find(int x)   //  Find the first one greater than or equal to x Value 
{
    
	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;  //  Mapping to  1,2,3 ... ( If from 0 Start mapping , No need to add 1)
}

Topic ideas ：

See the title here ： If the scope is 1e5, You can use prefixes and algorithms directly , The data range here is too large , Not suitable for prefixes and .

The problem solving steps ：

1. Sort （ Sort before you remove the duplicate ）
2. Remove duplicate numbers
3. Logical processing

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
//  here 3e10  Because n and m The range is 1e5,  Combined with the title, it is n + 2m  Operations 
const int N = 300010;   
int a[N], s[N]; // a  Indicates the number of saved , s  The prefix and 
int n, m;

vector<int> alls;  //  Used to save the relationship between real subscripts and mapped subscripts 
vector<PII> add, query; //  Save the value of the input operation 

//  Two points search ：  Find the result saved after discretization 
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;  //  Because the prefix and , So subscript from 1 It's convenient to start , No additional reprocessing of boundaries 
}
vector<int>:: iterator unique(vector<int> &a)  //  Double pointer implementation of library functions 
{
    
    int j = 0;
    for(int i = 0; i < a.size(); i ++)
        if(!i || a[i] != a[i - 1])
            a[j ++ ] = a[i];
           
    // a[0]~ a[j - 1]  all a Non repeating number in 
    return a.begin() + j;
}

int main()
{
    

    cin >> n >> m;
    for(int i = 0; i < n; i ++ )
    {
    
        int x, c;
        cin >> x >> c;
        add.push_back({
    x, c});  //  Insert operation reads 

        alls.push_back(x); // First put the subscript into the vector   Unified discretization 
    }

    for(int i = 0; i < m; i ++ )
    {
    
        int l, r;
        cin >> l >> r;
        query.push_back({
    l, r});   //  Read the discretization interval 

		//  Here we put all the subscripts in 
        alls.push_back(l);
        alls.push_back(r);
        // Map its left and right endpoints , The purpose is that we can find... In the virtual mapping table ,
		// This is very convenient for us to prefix and operate later . If we're in virtual 
		// When looking in the mapping table , If the left and right endpoints are not found , Then the prefix and cannot be found 
    }

    sort(alls.begin(), alls.end());  //  Sort 
    alls.erase(unique(alls), alls.end());  //  duplicate removal 
    // alls.erase(unique(alls.begin(), alls.end()), alls.end());

	// First map the elements in the add   assignment 
    for(auto item : add)   
    {
    
        int x = find(item.first);  // find x The mapping value of   Add... To the original array c
        a[x] += item.second; //  Handle insertion 
    }

	//  Handle prefixes and 
    for(int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];

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

    return 0;
}