zhangas

Pay more attention

0%

离散化

Posted on Edited on

利用vector存储映射的一组数据 

1
2
typedef pair<int,int> PII; 
vector<PII> add,query;//add是添加操作 query是查询操作

①先排序 再去重

1
2
unique函数的原型:
iterator unique(iterator it_1,iterator it_2);

返回值指向去重后容器中不重复序列的最后一个元素的下一元素

1
2
sort(all.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());

②二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int find(int x){
	int l=0,r=alls.size()-1;
	while(l<r){
		int mid=l+c>>1;
		if(alls[mid]>=x){
			r=mid;
		}
		else{
			l=mid+1;		
		}
	}
	//return l;//映射到0,1,2,3...
	return r+1;//映射到1,2,3,4s... 
        //在计算a的前缀和时 不需要考虑边界问题 s[i]=s[i-1]+a[i];
    
}

遍历add容器和求数组a的前缀和s

1
2
3
4
5
6
7
for(auto it:add){
		int x=find(it.first);
		a[x]+=it.second;
	} 
for(int i=0;i<=alls.size();i++){
    s[i]=s[i-1]+a[i];
}

遍历query容器输出

1
2
3
4
5
for(auto it:query){
    int l=find(it.first);
    int r=find(it,second);
    cout<<s[r]-s[l-1]<<endl;
}