[14. Interval sum (discretization)]

discretization

• Let's say there are 10⁵ Number , The range of each number is 0~10⁹, Some questions may use these value subscripts , But if we open a length of 10⁹ Arrays are unrealistic . And that's where it comes in mapping .
• We need to map this sequence from 1 At the beginning Continuous natural number , This process is called discretization .

nature

• The span of the whole range is very large , But very sparse , For example, there are 10⁹ Number , But we only used 10⁵ Number

step

• Going to the x Add a c, At this point, first find x The discretized value of k, And then again a[k] + c.
• It's also the same with prefix sum , seek [l, r] The sum of numbers between , First find l and r The value after discretization
  

Discretization needs to solve a problem

Premise a[ ] Is ordered .

• a[ ] Duplicate elements may appear in , It needs to be duplicate removal
• How to figure out x The discretized value of , It's usually used Two points
  

Interval and

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][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

Code

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

using namespace std;

using PII  = pair<int, int>; // Because the input is a pair , So use pair To hold the 
//typedef pair<int, int> PII;

const int N  = 300010;
int n, m;
int a[N], s[N];              //a[N] Is the number to store ,s[N] Are prefixes and 

vector<int> alls;            // All the discretized values we store 

vector<PII> add, query;      // The first is the insert operation , The second is to ask 

// First read in all the numbers , Put the used subscript , discretization .
int find(int x)              // Please x The result of discretization  
{
     
   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;            // Map numbers to subscripts from 1 Start , Because the interval is found later [l, r] The sum of middle numbers uses the prefix and , Subscript from 1, Don't deal with boundary problems 
}


int main()
{
     
   cin >> n >> m;
   for (int i = 0; i < n; i ++)
   {
     
       int x, c;
       cin >> x >> c;
       add.push_back({
     x, c});      // Put the number on add in 
       
       alls.push_back(x);             // Re count , Put it in the... To be discretized alls Array 
   }
   
   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());
   
   // Handle insertion 
   for (auto item : add)
   {
     
       int x = find(item.first);
       a[x] += item.second;
   }
   
   // Preprocessing prefixes and 
   for (int i = 1; i <= alls.size(); i ++) s[i] = s[i - 1] + a[i];
   
   // Inquiry before processing 
   for (auto item : query)
   {
     
       int l = find(item.first), r = find(item.second);
       cout << s[r] - s[l - 1] << endl;
   }
   return 0;
}

unique Implementation of function

vector<int>:: iterator unique(vector<int> &a)
{
   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;
}