Interval sum ----- discretization

discretization

Satisfy the property of discretization : The range of values is large , Sparse number
a[ ] : { 1 , 3 , 100 , 200 , 500000000 } mapping
Subscript :0 1 2 3 4
1.a[] There may be duplicate elements in duplicate removal
2. How to calculate the discrete value Two points ( This question is in order )

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] 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 −1e9≤x≤1e9,1≤n,m≤1e5,−1e9≤l≤r≤1e9,−10000≤c≤10000
sample input ：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
sample output :
8
0
5

#include<bits/stdc++.h>
using namespace std;
int n,m,l,r;
int const N=3e5+10;   // In the array x,l,c Corresponding to the discretized value , The number is the most 3*1e5
int a[N],s[N];     
vector<int> lisan;    // Store all discretized values 
typedef pair<int,int> PII;
vector<PII> addxc,xunwenlr;   // Insert x c;  Insert query l r;
int find(int x)     // Find the result of discretization 
{
      int l=0,r=lisan.size()-1;   
    while(l<r)
    {
     int mid=l+r >> 1;
         if(lisan[mid]>=x)   r=mid;
         else  l=mid+1;
    }
    return r+1;   // Coordinate addition 1, Map to from 1 Start ;
}
int main()
{
       cin>>n>>m;
  for(int i=0;i<n;i++)
    {
      int x,c;
        cin>>x>>c;
        lisan.push_back(x);
        addxc.push_back({
    x,c});
    }
    for(int i=0;i<m;i++)
    {
       cin>>l>>r;
        xunwenlr.push_back({
    l,r});
        lisan.push_back(l);
        lisan.push_back(r);
    }
      sort(lisan.begin(),lisan.end());
    lisan.erase(unique(lisan.begin(),lisan.end()),lisan.end());    // duplicate removal , Inserted x l r  Remove the same 
    for(auto item:addxc)    // Insert processing 
    {
       int xx=find(item.first);   //xx The subscript corresponding to discretization 
        a[xx]+=item.second;
    }
    for(int i=1;i<=lisan.size();i++) // The prefix and 
        s[i]=s[i-1]+a[i]; 
    for(auto item:xunwenlr)   // Deal with inquiries 
    {
       l=find(item.first);  // The subscript corresponding to discretization 
        r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }        
     return 0;
     }

// Remove the weight from the top unique Functions and erase function   Source code 
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];
  Return a.begin()+j;
}

unique() function , The following elements replace the previous repeated elements , Generally, it is used after sorting ( The adjacent elements are removed ), The space behind has not been deleted

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    
	int a[]={
    2,3,4,4,6};
	sort(a,a+5);              // Generally in use unique It needs to be sorted before ;
	unique(a,a+5);           // Use unique The array de duplication function 
	for(int i=0;i<5;i++)
	{
      cout<<a[i]<<” “;       // 2 3 4 6 6
	}
	cout<<" The length of the non repeating sequence ："<<unique(a,a+5)-a<<endl;   // The length of the unrepeated sequence :4 
}