337 字

1 分钟

位运算、离散化和区间合并算法学习

2022-07-16

algorithm

/

acwing

1. 位运算#

1.1 使用背景#

在进行位运算时，我们可以将数看为二进制数，而位运算也就是对于数特定位置的值进行运算。

1.2 例题#

801. 二进制中1的个数

在找数字中的1的时候有两种常用方法。

当1<<i & x = 1时，第i位存在1
lowbit(x) = x & -x找出末位的1

参考代码：

1
int lowbit(int x){
2
    return x & -x;
3
}
4
void solve(){
5
  for(int i=0;i<n;i++){
6
        cin>>t;
7
        int cnt = 0;
8
        for(;t;t -= lowbit(t)) cnt++;
9
        cout<<cnt<<' ';
10
    }
11
}

2. 离散化#

2.1 使用背景#

当获得的数据是在较长的范围内呈稀疏分布，为了节省使用的空间以及搜索数据的速度，我们使用了离散化对数据进行处理。

2.2 例题#

802. 区间和

对于查询问题，我们可以通过前缀和在o(1)内求出，所以该问题的重点主要在于对于数据的离散化。

可以发现在数轴上要使用的数有插入位置x、查询左右范围l,r共三个数，将这三个数存入离散化后的数组中，并保持其位置与原数组位置的映射即可。

参考代码：

1
void solve(){
2
    cin>>n>>m;
3
    for(int i=0;i<n;i++){
4
        cin>>x>>c;
5
        if(a[x]) a[x] += c;
6
        else a[x] = c;
7
        all.push_back(x);
8
    }
9
    while(m--){
10
        cin>>l>>r;
11
        q.push_back({l,r});
12
        all.push_back(l);
13
        all.push_back(r);
14
    }
15
    sort(all.begin(),all.end());
16
    all.erase(unique(all.begin(),all.end()),all.end());
17

18
    for(int i=1;i<=all.size();i++){
19
        int t = a[all[i-1]];
20
        s[i] = t + s[i-1];
21
    }
22
    for(auto i:q){
23
        l = lower_bound(all.begin(),all.end(),i.first)-all.begin();
24
        r = lower_bound(all.begin(),all.end(),i.second)-all.begin();
25
        cout<<s[r+1] - s[l]<<endl;
26
    }
27
}

3. 区间合并#

3.1 使用背景#

快速对多个区间进行合并，对区间按首端点排序后，判断是否覆盖即可。

3.2 例题#

803. 区间合并

参考代码：

1
void solve(){
2
    for(int i=0;i<n;i++){
3
        cin>>l>>r;
4
        a.push_back({l,r});
5
    }
6
    sort(a.begin(),a.end(),[](PII t1,PII t2){
7
        return t1.first < t2.first;
8
    });
9
    int al = -2e9,ar = -2e9;
10
    for(auto i : a){
11
        int ml = i.first,mr = i.second;
12
        if(ml > ar){
13
            ans ++;
14
            al = ml;ar = mr;
15
        }else if(mr > ar){
16
            ar = mr;
17
        }
18
    }cout<<(ans ? ans : 1)<<endl;
19
}

206 字

1 分钟

Algorithm Study: Bitwise Operations, Discretization, and Interval Merging

2022-07-16

algorithm

/

acwing

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#

801. Number of 1s in Binary

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 & -x to find the least significant 1

Reference code:

1
int lowbit(int x){
2
    return x & -x;
3
}
4
void solve(){
5
  for(int i=0;i<n;i++){
6
        cin>>t;
7
        int cnt = 0;
8
        for(;t;t -= lowbit(t)) cnt++;
9
        cout<<cnt<<' ';
10
    }
11
}

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#

802. Range Sum

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:

1
void solve(){
2
    cin>>n>>m;
3
    for(int i=0;i<n;i++){
4
        cin>>x>>c;
5
        if(a[x]) a[x] += c;
6
        else a[x] = c;
7
        all.push_back(x);
8
    }
9
    while(m--){
10
        cin>>l>>r;
11
        q.push_back({l,r});
12
        all.push_back(l);
13
        all.push_back(r);
14
    }
15
    sort(all.begin(),all.end());
16
    all.erase(unique(all.begin(),all.end()),all.end());
17

18
    for(int i=1;i<=all.size();i++){
19
        int t = a[all[i-1]];
20
        s[i] = t + s[i-1];
21
    }
22
    for(auto i:q){
23
        l = lower_bound(all.begin(),all.end(),i.first)-all.begin();
24
        r = lower_bound(all.begin(),all.end(),i.second)-all.begin();
25
        cout<<s[r+1] - s[l]<<endl;
26
    }
27
}

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#

803. Merge Intervals

Reference code:

1
void solve(){
2
    for(int i=0;i<n;i++){
3
        cin>>l>>r;
4
        a.push_back({l,r});
5
    }
6
    sort(a.begin(),a.end(),[](PII t1,PII t2){
7
        return t1.first < t2.first;
8
    });
9
    int al = -2e9,ar = -2e9;
10
    for(auto i : a){
11
        int ml = i.first,mr = i.second;
12
        if(ml > ar){
13
            ans ++;
14
            al = ml;ar = mr;
15
        }else if(mr > ar){
16
            ar = mr;
17
        }
18
    }cout<<(ans ? ans : 1)<<endl;
19
}

441 字

1 分钟

アルゴリズム学習：ビット演算・離散化・区間マージ

2022-07-16

algorithm

/

acwing

1. ビット演算#

1.1 背景#

ビット演算を行う際には、数を二進数としてみなし、ビット演算は数の特定の位置にある値に対して演算を行うものです。

1.2 練習問題#

801. 二進数の中の1の個数

数の中の1を探すときには、主に2つの方法があります。

当1<<i & x = 1のとき、第iビットには1が存在します
lowbit(x) = x & -xを用いて末尾の1を見つける

参考コード：

1
int lowbit(int x){
2
    return x & -x;
3
}
4
void solve(){
5
  for(int i=0;i<n;i++){
6
        cin>>t;
7
        int cnt = 0;
8
        for(;t;t -= lowbit(t)) cnt++;
9
        cout<<cnt<<' ';
10
    }
11
}

2. 離散化#

2.1 背景#

取得したデータが長い範囲にわたって疎に分布している場合、使用するメモリを節約しデータを検索する速度を高めるために、データを離散化して処理します。

2.2 練習問題#

802. 区間和

クエリ問題については、累積和を用いることで O(1) 内に求められるため、この問題の焦点はデータの離散化にあります。

数軸上で使用するべき数は挿入位置x、左右の範囲を表すl,rの3つであり、これら3つの数を離散化後の配列に格納し、それぞれの位置を元の配列の位置と対応づけておけばよい。

参考コード：

1
void solve(){
2
    cin>>n>>m;
3
    for(int i=0;i<n;i++){
4
        cin>>x>>c;
5
        if(a[x]) a[x] += c;
6
        else a[x] = c;
7
        all.push_back(x);
8
    }
9
    while(m--){
10
        cin>>l>>r;
11
        q.push_back({l,r});
12
        all.push_back(l);
13
        all.push_back(r);
14
    }
15
    sort(all.begin(),all.end());
16
    all.erase(unique(all.begin(),all.end()),all.end());
17

18
    for(int i=1;i<=all.size();i++){
19
        int t = a[all[i-1]];
20
        s[i] = t + s[i-1];
21
    }
22
    for(auto i:q){
23
        l = lower_bound(all.begin(),all.end(),i.first)-all.begin();
24
        r = lower_bound(all.begin(),all.end(),i.second)-all.begin();
25
        cout<<s[r+1] - s[l]<<endl;
26
    }
27
}

3. 区間合併#

3.1 背景#

複数の区間を高速にマージするには、区間を開始点でソートし、被覆しているかどうかを判断すればよい。

3.2 練習問題#

803. 区間合併

参考コード：

1
void solve(){
2
    for(int i=0;i<n;i++){
3
        cin>>l>>r;
4
        a.push_back({l,r});
5
    }
6
    sort(a.begin(),a.end(),[](PII t1,PII t2){
7
        return t1.first < t2.first;
8
    });
9
    int al = -2e9,ar = -2e9;
10
    for(auto i : a){
11
        int ml = i.first,mr = i.second;
12
        if(ml > ar){
13
            ans ++;
14
            al = ml;ar = mr;
15
        }else if(mr > ar){
16
            ar = mr;
17
        }
18
    }cout<<(ans ? ans : 1)<<endl;
19
}

位运算、离散化和区间合并算法学习

https://dreaife.tokyo/posts/bitwise-algorithm/

作者

dreaife

发布于

2022-07-16

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

满载的梦想与希望，自我的宽恕与畅想——樱花摸鱼

前缀和、差分和双指针算法学习

dreaife的休憩小栈

1. 位运算#

1.1 使用背景#

1.2 例题#

2. 离散化#

2.1 使用背景#

2.2 例题#

3. 区间合并#

3.1 使用背景#

3.2 例题#

1. Bitwise Operations#

1.1 Background#

1.2 Example problems#

2. Discretization#

2.1 Background#

2.2 Example problems#

3. Interval Merging#

3.1 Background#

3.2 Example problems#

1. ビット演算#

1.1 背景#

1.2 練習問題#

2. 離散化#

2.1 背景#

2.2 練習問題#

3. 区間合併#

3.1 背景#

3.2 練習問題#