206 words
1 minute
Algorithm Study: Bitwise Operations, Discretization, and Interval Merging
1. Bitwise Operations
1.1 Background
When performing bit operations, we can view numbers as binary, and bitwise operations operate on the value at specific positions in the number.
1.2 Example problems
There are two common methods for finding the number of 1s in a number.
- When
1<<i & x = 1, the i-th bit is 1 lowbit(x) = x & -xto find the least significant 1
Reference code:
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. Discretization
2.1 Background
When the obtained data are sparsely distributed over a wide range, to save space and speed up data searching, we use discretization to process the data.
2.2 Example problems
For query problems, we can obtain it in O(1) via prefix sums, so the key of this problem lies mainly in data discretization.
It can be seen that on the number line the numbers we need to use are the insertion position x, and the left and right query ranges l,r — a total of three numbers. Put these three numbers into the discretized array and maintain their mapping to the original array positions.
Reference code:
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. Interval Merging
3.1 Background
Quickly merge multiple intervals by sorting the intervals by their left endpoints and checking for overlaps.
3.2 Example problems
Reference code:
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;} Share
If this article helped you, please share it with others!
Algorithm Study: Bitwise Operations, Discretization, and Interval Merging
https://dreaife.tokyo/en/posts/bitwise-algorithm/ Some information may be outdated
Dreams and Hope Overflowing, Self-Forgiveness and Reverie — Sakura, Moyu.
Algorithm Study: Prefix Sum, Difference Array, and Two Pointers
Related Posts Smart
1
Algorithm Study: Prefix Sum, Difference Array, and Two Pointers
algorithm This article introduces the principles and applications of prefix sums, difference arrays, and the two-pointer technique. Prefix sums are used to quickly compute subarray sums, difference arrays are used to efficiently handle range updates, and the two-pointer method optimizes query efficiency by maintaining pointers. Related examples and reference code are provided to help understand and apply these algorithms.
2
Sorting and Binary Search Study Notes
algorithm This article introduces the principles and implementations of quicksort and merge sort, including time complexity and related problems. Quicksort partitions the sequence into two parts around a midpoint, while merge sort merges sorted subarrays. It also discusses binary search algorithms for integers and floating-point numbers and their implementations.
3
High-Precision Arithmetic Study Notes
algorithm High-precision arithmetic includes addition, subtraction, multiplication, and division for large numbers that exceed the range of ordinary data types. Addition and subtraction are implemented by simulating manual calculation, while multiplication and division process digits step by step and pay attention to removing leading zeros. Related examples and reference code are provided to help understand and implement these operations.
4
Interview Algorithm Study 1
algorithm This post contains multiple algorithm interview problems and solutions, including snake matrix filling, quicksort on a singly linked list, finding peaks and local minima, the egg hardness problem, a stack supporting minimum retrieval, and finding the entry node of a cycle in a linked list. Each problem includes a detailed description, input/output format, and sample code.
5
The First Round of Selection in the New Era
life With the development of AI technology, the cost of using advanced models may lead to social stratification, where only those with strong financial means can use these models. Although current prices are still acceptable, future price increases may make them unaffordable for most people, thus forming the first round of selection. The author feels anxious about this phenomenon, while also realizing that AI applications have moved beyond programming and into broader industries. Facing the challenges and opportunities of a new world, individuals continue to explore under the momentum of the times.
Random Posts Random