这些是我稍微学会后的想法与理解,如有错误与不到之处还望赐教
离散化思想:通过 中间数组 达到将原数据映射到 自定义数组 中去。
此题中中间数组应保存询问数据,因为仍是通过中间数组去查询
题目描述
blablabla
样例
blablabla
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=3e5+10; //数据在1e5上有三个
int a[N],s[N]; //a数组为映射数组
typedef pair<int,int> p;
vector<p> add,q; //定义add(用来实现 加 操作),定义q(保存询问)
vector<int> t; //定义t(中间数组,实现映射操作)
int f(int x){ //二分实现查找,并映射
int l=0, r=t.size()-1;
while(l<r){
int mid=l+r>>1;
if(t[mid]>=x) r=mid;
else l=mid+1;
}
return r+1; //映射下标从一开始
}
int main(){
int n,m;
cin>>n>>m;
while(n--){
int x,c;
cin>>x>>c;
add.push_back({x,c}); //将 加 相关操作放入add
t.push_back(x); //中间数组先存放x
}
while(m--){
int l,r;
cin>>l>>r;
q.push_back({l,r}); //询问数组存放 询问 相关操作
t.push_back(l), t.push_back(r); //为什么把 l,r 也存入数组,往后看
}
sort(t.begin(),t.end()); //排序并去重
t.erase(unique(t.begin(),t.end()),t.end()); //为什么要去重,在此题中 询问 可能会与 加 重复,影响映射下标
for(auto u: add){
int x=f(u.first);
a[x]+=u.second; //通过t数组实现 加 操作,并映射下标
}
for(int i=1;i<=t.size();i++) s[i]=s[i-1]+a[i]; //前缀和
for(auto u: q){
int l=f(u.first), r=f(u.second); //最后询问操作,在中间数组中已存放,即 l,r在 t中
cout<<s[r]-s[l-1]<<endl;
}
}
思考:此题去重是 询问与加 同时有重复。
仅加重复,会影响吗? 不会,add未去重,遍历仍加,t中查找不影响映射下标
仅询问重复,会影响吗? 不会,t去重且q保留询问