337 字
1 分钟
位运算、离散化和区间合并 算法学习
1. 位运算
1.1 使用背景
在进行位运算时，我们可以将数看为二进制数，而位运算也就是对于数特定位置的值进行运算。
1.2 例题
在找数字中的1的时候有两种常用方法。
- 当
1<<i & x = 1时，第i位存在1 lowbit(x) = x & -x找出末位的1
参考代码：
int lowbit(int x){ return x & -x;}void solve(){ for(int i=0;i<n;i++){ cin>>t; int cnt = 0; for(;t;t -= lowbit(t)) cnt++; cout<<cnt<<' '; }}2. 离散化
2.1 使用背景
当获得的数据是在较长的范围内呈稀疏分布，为了节省使用的空间以及搜索数据的速度，我们使用了离散化对数据进行处理。
2.2 例题
对于查询问题，我们可以通过前缀和在o(1)内求出，所以该问题的重点主要在于对于数据的离散化。
可以发现在数轴上要使用的数有插入位置x、查询左右范围l,r共三个数，将这三个数存入离散化后的数组中，并保持其位置与原数组位置的映射即可。
参考代码：
void solve(){ cin>>n>>m; for(int i=0;i<n;i++){ cin>>x>>c; if(a[x]) a[x] += c; else a[x] = c; all.push_back(x); } while(m--){ cin>>l>>r; q.push_back({l,r}); all.push_back(l); all.push_back(r); } sort(all.begin(),all.end()); all.erase(unique(all.begin(),all.end()),all.end());
for(int i=1;i<=all.size();i++){ int t = a[all[i-1]]; s[i] = t + s[i-1]; } for(auto i:q){ l = lower_bound(all.begin(),all.end(),i.first)-all.begin(); r = lower_bound(all.begin(),all.end(),i.second)-all.begin(); cout<<s[r+1] - s[l]<<endl; }}3. 区间合并
3.1 使用背景
快速对多个区间进行合并，对区间按首端点排序后，判断是否覆盖即可。
3.2 例题
参考代码：
void solve(){ for(int i=0;i<n;i++){ cin>>l>>r; a.push_back({l,r}); } sort(a.begin(),a.end(),[](PII t1,PII t2){ return t1.first < t2.first; }); int al = -2e9,ar = -2e9; for(auto i : a){ int ml = i.first,mr = i.second; if(ml > ar){ ans ++; al = ml;ar = mr; }else if(mr > ar){ ar = mr; } }cout<<(ans ? ans : 1)<<endl;} 分享
如果这篇文章对你有帮助，欢迎分享给更多人！
位运算、离散化和区间合并 算法学习
https://dreaife.tokyo/cn/bitwise-algorithm/ 部分信息可能已经过时
相关文章 智能推荐
1
前缀和、差分和双指针 算法学习
algorithm 介绍了前缀和、差分和双指针算法的原理和应用。前缀和用于快速计算数组区间和，差分用于高效处理区间更新，双指针法通过维护指针来优化查询效率。提供了相关例题及参考代码以帮助理解和应用这些算法。
2
高精度 学习记录
algorithm 高精度运算包括加法、减法、乘法和除法，适用于处理超出常规数据类型范围的大数。加法和减法通过模拟手动计算实现，乘法和除法则依次处理每位数字，注意前导零的去除。提供了相关的例题和参考代码以帮助理解和实现这些运算。
3
排序 二分学习
algorithm 介绍了快速排序和归并排序的原理及实现，包括时间复杂度和相关题目。快速排序通过选取中点将数列分为两部分进行排序，归并排序则将已排序的子段合并。还讨论了整数和浮点数的二分查找算法及其实现方法。
4
面试算法学习1
algorithm 包含多个算法面试题及其解法，包括蛇形矩阵填充、单链表快速排序、寻找峰值、极小值、鸡蛋硬度问题、支持最小值检索的栈以及链表中环的入口节点的查找。每个题目附有详细描述、输入输出格式和示例代码。
5
新时代的第一轮筛选
life 随着AI技术的发展，使用先进模型的成本可能导致社会分层，只有经济能力强的人才能使用这些模型。虽然当前价格尚可，但未来价格的上涨可能使大多数人无法承担，从而形成第一轮筛选。作者对这种现象感到焦虑，同时也意识到AI的应用已超越编程领域，进入更广泛的产业。面对新世界的挑战与机遇，个人在时代的推动下不断探索。