acwing算法基础课文字版（看不懂你打我）——第三课基础算法之：双指针算法/位运算

写在前面：acwing是由北大学长创立的算法学习平台，在IT资源良莠不齐的当下异军突起。只需一顿火锅钱，就能跟着获得noi金牌的北大学长学习算法，是IT初学者进行深入研究的不二平台。本系列帖子将围绕AcWing平台的主打课程——算法基础课，并辅以本人自己的学习心得与广大算法爱好者分享知识。如果觉得本篇内容对你有帮助的话，希望不吝点赞。若有不同看法的话欢迎在评论区友善探讨。下面附上AcWing平台的地址，强烈推荐大家去学习视频课程哦！！！
链接：https://www.acwing.com/activity/content/introduction/11/
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

前置知识

算法，对于学习计算机软件相关的同学来说，无论是求职还是升学，都是不可避免的一环。

当我们面对常规的算法题时，往往对于解题速度有着一定的要求。

但当我们面对不常规的算法题时，考验我们思维深度的同时也对基础算法的掌握程度有了苛刻的要求，如果对基础算法的掌握不牢固的话，很难更进一步。

。所以，本系列将结合AcWing平台提供的基础算法模板进行算法硬核干货讲解。

理解并熟悉 本系列的基础算法，将对同学们的求职升学都带来极大帮助，对于类似蓝桥杯等比赛也能轻松拿下！

离散化

该课程，总共七章，平均每章三节课左右。视频总共45小时，这里是第一章第三节课的离散化部分。

算法原理

 #include<iostream>
 #include<vector>
 #include<algorithm>
 
 using namespace std;
 
 typedef pair<int, int> PII;
 
 const int N = 300010;
 
 int n,m;
 int a[N],s[N];
 
 vector<int> alls;
 vector<PII> add, query;
 
 int find(int x)
 {
 	int l = 0, r = alls.size() - 1;
 	while(l < r){
 		int mid = l + r >> 1;
 		if(alls[mid] >= x) r = mid;
 		else l = mid + 1;
 	}
 	return r + 1;
 }
 
 //unique函数怎么实现的，java和python没有


/*
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];
 	//a[0] ~a[j - 1]所有a中不重复的数		
 	
	 return a.begin() + j;		
 } 
 
 //下面的函数体部分改成 alls.erase(unique(alls),alls.end()); 
 
*/ 

 
 
 int main()
 {
 	cin >> n >>m;
 	for(int i = 0; i < n; i++){
 		int x, c;
 		cin >> x >> c;
 		add.push_back({x,c});
 		
 		alls.push_back(x); 
 	}
 	
 	for(int i = 0; i < m; i++){
 		int l ,r;
 		cin >> l >>r;
 		query.push_back({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);
	 	a[x] += item.second;
	 }
	 
	 //预处理前缀和
	 for(int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
	 
	 //预处理询问
	 
	 for(auto item : query){
	 	int l = find(item.first),r = find(item.second);
	 	cout << s[r] - s[l - 1] << endl;
	 } 
	 
	 return 0;
}

补充说明