区间和------离散化

离散化

满足离散化的性质:值域大,数稀疏
a[ ] : { 1 , 3 , 100 , 200 , 500000000 } 映射
下标:0 1 2 3 4
1.a[]中可能有重复的元素 去重
2.如何计算出离散化的值 二分(此题有序)

区间和

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。现在，我们首先进行 n 次操作，每次操作将某一位置 x上的数加 c。接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。输入格式:第一行包含两个整数 n 和 m。接下来 n 行，每行包含两个整数 x 和 c。再接下来 m 行，每行包含两个整数 l 和 r。输出格式:共 m 行，每行输出一个询问中所求的区间内数字和。数据范围−1e9≤x≤1e9,1≤n,m≤1e5,−1e9≤l≤r≤1e9,−10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5

#include<bits/stdc++.h>
using namespace std;
int n,m,l,r;
int const N=3e5+10;   //数组里面存x,l,c对应离散化的值,个数最多3*1e5
int a[N],s[N];     
vector<int> lisan;    //存入所有离散化的值
typedef pair<int,int> PII;
vector<PII> addxc,xunwenlr;   //插入x c; 插入询问l r;
int find(int x)     //求离散化的结果
{
      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;   //坐标加1,映射到从1开始;
}
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());    //去重,插入的x l r 去掉相同的
    for(auto item:addxc)    //插入处理
    {
       int xx=find(item.first);   //xx离散化所对应的下标
        a[xx]+=item.second;
    }
    for(int i=1;i<=lisan.size();i++) //前缀和
        s[i]=s[i-1]+a[i]; 
    for(auto item:xunwenlr)   //处理询问
    {
       l=find(item.first);  //离散化所对应的下标
        r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }        
     return 0;
     }

//上面去重unique函数和erase函数 原代码
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()函数,后面的元素替换的前面重复的元素,一般排序后使用(去除的是相邻元素),后面的空间并没有删除掉

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    
	int a[]={
    2,3,4,4,6};
	sort(a,a+5);              //一般在使用unique之前都需要进行排序;
	unique(a,a+5);           //使用unique函数对数组进行去重
	for(int i=0;i<5;i++)
	{
      cout<<a[i]<<” “;       // 2 3 4 6 6
	}
	cout<<"不重复数列的长度："<<unique(a,a+5)-a<<endl;   //不重复序列的长度:4 
}