算法总结—倍增

LRRabcd · 2025-01-08 23:27:08 · 个人记录

倍增

倍增分两步：

• 倍增
• 二进制拆解

拿道题来理解一下： ١١(❛ᴗ❛)【倍增】-最小线段合并

这道题用倍增 AC 不了，但可以用来理解倍增原理，以 n=26 来举例。定义两个变量 cnt=0,len=1。

• cnt+len<=n;cnt+=len;len*=2，cnt=1,len=2

• cnt+len<=n;cnt+=len;len*=2，cnt=3,len=4

• cnt+len<=n;cnt+=len;len*=2，cnt=7,len=8

• cnt+len<=n;cnt+=len;len*=2，cnt=15,len=16

上面都是倍增得部分，下面是二进制拆解

• cnt+len>n;len/=2，cnt=15,len=8

• cnt+len<=n;cnt+=len;len*=2，cnt=23,len=16

• cnt+len>n;len/=2，cnt=23,len=8

• cnt+len>n;len/=2，cnt=23,len=4

• cnt+len>n;len/=2，cnt=23,len=2

• cnt+len<=n;cnt+=len;len*=2，cnt=25,len=4

• cnt+len>n;len/=2，cnt=25,len=2

• cnt+len>n;len/=2，cnt=25,len=1

• cnt+len<=n;cnt+=len;len*=2，cnt=26,len=2,cnt==n 程序结束。

代码

不可 AC

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int cnt=0;
    int len=1;
    while(len){
        if(cnt+len<=n){
            cnt+=len;
            len*=2;
        }else{
            len/=2;
        }
    }
    return 0;
}

可 AC，但不是倍增

#include<bits/stdc++.h>
#define int long long
using namespace std;
int p[35];
signed main(){
    int n;
    cin>>n;
    if(n==0){
        cout<<-1;
        return 0;
    }
    p[0]=1;
    for(int i=1;i<=31;i++){
        p[i]=p[i-1]*2;
    }
    int cnt=0;
    int ans=0;
    for(int i=31;i>=0;i--){
        cnt+=n/p[i];
        n%=p[i];
    }
    cout<<cnt;
    return 0;
}

١١(❛ᴗ❛)【倍增】-右侧最大下标

• 若 cnt+len<=n&&a[cnt+len]<m，倍增，cnt+=len;len*=2。

• 否则 二进制拆解，len/=2。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[10005];
void work(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int cnt=0;
    int len=1;
    while(len){
        if(cnt+len<=n&&a[cnt+len]<m){
            cnt+=len;
            len*=2;
        }else{
            len/=2;
        }
    }
    if(a[cnt]<m){
        cout<<a[cnt]<<"\n";
    }else{
        cout<<"-1\n";
    }
    return;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        work();
    } 
    return 0;
}

١١(❛ᴗ❛)【倍增】-最大k值和

与上一道题类似，只是 a 数组变为了表示 a 数组前缀和的 sum 数组。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[10005];
int sum[10005];
signed main(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    while(q--){
        int x;
        cin>>x;
        int cnt=0;
        int len=1;
        while(len){
            if(cnt+len<=n&&sum[cnt+len]<x){
                cnt+=len;
                len*=2;
            }else{
                len/=2;
            }
        }
        cout<<cnt<<"\n";
    }
    return 0;
}

以上代码的时间复杂度为 O(n\log n)。

ST 表

ST 表又称稀疏表，用到了倍增的思想，主要用来求解重复的区间不会影响答案的问题，比如求一个区间内的 \max,\min\gcd\text{lcm}。

ST 表主要是一个 DP 数组，dp_{i,j} 表示以 i 为起点，长度为 2^j 的区间的答案。

以 \max 来举例。

初始化

首先每一个 dp_{i,0}=a_i，每一个大区间 [i,i+2^{j}-1] 可以分成两个长度相等的小区间 [i,i+2^{j-1}-1] 和 [i+2^{j-1},i+2^{j}-1]，这两个区间的最大值分别是 dp_{i,j-1} 和 dp_{i+2^{j-1},j-1}，所以 dp_{i,j}=\max(dp_{i,j-1},dp_{i+2^{j-1},j-1})，时间复杂度 O(n\log n)。

查询

一个区间 [l,r] 可以被两个长度相等的区间覆盖(可能有重叠，但没有关系)，这两个区间的长度都是 k=\log (r-l+1) ，那么这两个区间的最大值就分别是 dp_{l,k} 和 dp_{r-2^k+1,k}，所以 \max\{a_l,a_{l+1},\dots,a_r\}=\max(dp_{l,k},dp_{r-2^k+1,k})，时间复杂度 O(1)。

【模板】ST 表 && RMQ 问题

按上面的方法写就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[100005];
int dp[100005][35];
void st(){
    int N=log2(n);
    for(int j=1;j<=N;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        }
    }
    return;
}
int query(int l,int r){
    int k=log2(r-l+1);
    int ans=max(dp[l][k],dp[r-(1<<k)+1][k]);
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[i][0]=a[i];
    }
    st();
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<query(l,r)<<"\n";
    }
    return 0;
}

[JSOI2008] 最大数

这道题是伪在线，所以也可以用 ST 表实现，我们可以发现修改一个数 a_{cnt} 只会影响到所有 dp_{cnt-2^j+1,j} 的值，每次修改就只需要 O(\log n) 的时间，注意每次修改时要初始化一个 dp 值：dp_{cnt,0}=a_{cnt}。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[200005][25];
void add(int id,int val){
    dp[id][0]=val;
    for(int i=1;i<=20;i++){
        if((id-(1<<i))<0){
            break;
        }
        dp[id-(1<<i)+1][i]=max(dp[id-(1<<i)+1][i-1],dp[id-(1<<(i-1))+1][i-1]);
    }
    return;
}
int query(int l,int r){
    int k=log2(r-l+1);
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int q,mod;
    cin>>q>>mod;
    int last=0;
    int cnt=0;
    while(q--){
        char op;
        cin>>op;
        if(op=='Q'){
            int x;
            cin>>x;
            last=query(cnt-x+1,cnt);
            cout<<last<<"\n";
        }else{
            int x;
            cin>>x;
            cnt++;
            add(cnt,(x+last)%mod);
        }
    } 
    return 0;
}

[JRKSJ R1] JFCA

这道题是个环怎么办，断环成链，但是这里既要向左边找，又要向右边找，所以得把原数组复制两遍，空间变为 3n。接着根据长度越长，最大值单调不减的单调性直接二分距离即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int a[300005];
int b[300005];
int dp[300005][25];
void st(){
    int N=log2(n);
    for(int j=1;j<=N;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
        }
    }
    return;
}
int query(int l,int r){
    int k=log2(r-l+1);
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
bool check(int x,int i){
    int p=query(i-x,i-1);
    int q=query(i+1,i+x);
    return max(p,q)>=b[i];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=n;i++){
        a[i+n]=a[i];
    }
    for(int i=1;i<=n;i++){
        a[i+n+n]=a[i];
    }
    for(int i=1;i<=n;i++){
        b[i+n]=b[i];
    }
    for(int i=1;i<=n;i++){
        b[i+n+n]=b[i];
    }
    n*=3;
    for(int i=1;i<=n;i++){
        dp[i][0]=a[i];
    }
    st();
    for(int i=n/3+1;i<=n/3*2;i++){
        int l=0,r=n/3;
        while(l+1<r){
            int mid=(l+r)/2;
            if(check(mid,i)){
                r=mid;
            }else{
                l=mid;
            }
        } 
        if(r==n/3){
            cout<<-1<<" ";
        }else{
            cout<<r<<" ";
        }
    }
    return 0;
}

FREQUENT - Frequent values

设 mp[a[i]] 为 1 到 i 种 a_i 出现的次数，ST 表中 dp_{i,0} 就等于 mp_{a_i}，每次找答案时，求最大值即可，不过，这样答案有问题，因为最大的那个数可能在边界上，不全，所以还需要一个数组 R_{a_i} 表示 a_i 最后出现的位置，答案就是 \max(R_{a_l}-l+1,\text{query}(R_{a_l}+1,r))。

代码

#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[100005];
int dp[100005][35];
map<int,int>mp,R;
void st(){
    int N=log2(n);
    for(int j=1;j<=N;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
        }
    }
    return;
}
int query(int l,int r){
    int k=log2(r-l+1);
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(1){
        cin>>n;
        if(n==0){
            return 0;
        }
        cin>>q;
        mp.clear();
        R.clear();
        for(int i=1;i<=n;i++){
            cin>>a[i];
            mp[a[i]]++;
            dp[i][0]=mp[a[i]];
            R[a[i]]=i;
        }
        st();
        while(q--){
            int l,r;
            cin>>l>>r;
            if(l>r){
                swap(l,r);
            }
            if(a[l]==a[r]){
                cout<<r-l+1<<"\n";
            }else{
                cout<<max(R[a[l]]-l+1,query(R[a[l]]+1,r))<<"\n";
            }
        }
    }
    return 0;
}