10 离散化

离散化就是一一对应的关系 

//求区间和
#include
using namespace std;
typedef pair PII;//定义一个PII来存要读入的两个数，也就是区间
const int N=3e5+10;//开三十万是因为x+l+r
int a[N],s[N];//a是读入的数，s是前缀和
vector alls;//alls是存我们所有要离散化的值
vector add,query;//一个是插入两个数的 *** 作，另一个询问两个数区间的 *** 作
int find(int x)//作用是求一下x这个值离散化后的结果
{
    int l=0,r=alls.size()-1;
    //二分寻找
    while(l>1;
        if(alls[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r+1;//因为询问的是自然数，而我们存的是从0开始，所以得加上1使得下标从1开始
}
int main()
{
  int n,m;
  cin>>n>>m;
   for(int i=0;i>x>>c;
       add.push_back({x,c});//把x下标加上c
        alls.push_back(x);//把x加入待离散化的数组里面去
   }
   for(int i=0;i>l>>r;//读入询问区间
       query.push_back({l,r});//把l,r加到询问的数组里面去
       alls.push_back(l);
       alls.push_back(r);//把区间所有加到待离散化数组里面去
   }
//下面进行离散化的步骤
//去重
sort(alls.begin(),alls.end());//将所有值排序
alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重
//处理插入
for(auto item:add)
{
    int x=find(item.first);//add有两个数第一个是下标第二个是c要插入的数
    a[x]+=item.second;//把离散化的下标加上c后放进a数组里头
}
//预处理前缀和
for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];//s是a的前缀和
//处理询问
for(auto item:query)
{
    int l=find(item.first),r=find(item.second);//first和second是之前存进query的两个数
    cout< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5702738.html