【每周算法】第十一周：倍增

· 2025-11-26 · # 每周算法 # 学习笔记 # 编程

笔记

这一周主要是ST表解决RMQ问题，然后由于我比较懒就直接扔一篇别人的文章了：https://www.cnblogs.com/yoke/p/6949838.html

Luogu P1816 忠诚

倍增我不大熟，但线段树倒是还可以，这题也是每看出一点是可以用倍增做的

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
int a[N],tr[N*4];
void build(int x,int l,int r){
    if(l == r){
        tr[x] = a[l];
        return;
    }
    int mid = (l+r)/2,idx = x*2;
    build(idx,l,mid);
    build(idx+1,mid+1,r);
    tr[x] = min(tr[idx],tr[idx+1]);
}
int gt(int x,int l,int r,int l1,int r1){
    if(l == l1 && r == r1){
        return tr[x];
    }
    int mid = (l+r)/2,idx = x*2;
    if(r1 <= mid){
        return gt(idx,l,mid,l1,r1);
    } else if(l1 > mid){
        return gt(idx+1,mid+1,r,l1,r1);
    } else{
        return min(gt(idx,l,mid,l1,mid),gt(idx+1,mid+1,r,mid+1,r1));
    }
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d ",gt(1,1,n,l,r));
    }
    return 0;
}

（补：哦，原来是我RMQ都是一点印象没了，赶紧补课吧)

Luogu P1226 【模板】快速幂

快速幂的模板题

#include<bits/stdc++.h>

using namespace std;

int main(){
    long long a;
    int b,p;
    scanf("%lld%d%d",&a,&b,&p);
    long long ans = 1;
    int ac = a,bc = b;
    while(b){
        if(b&1){
            ans = (ans*a)%p;
        }
        a = (a*a)%p;
        b >>= 1;
    }
    printf("%d^%d mod %d=%lld",ac,bc,p,ans);
    return 0;
}

Luogu P3865 【模板】ST 表 & RMQ 问题

666，回去补了一下课，也是终于把ST表给想起来了

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
int a[N],f[N][25];
void read(int& x){
    x = 0;
    int f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-'){
            f = -1;
        }
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x *= 10;
        x += (c-'0');
        c = getchar();
    }
    x *= f;
}

int main(){
    // freopen("1.in","r",stdin);
    int n,m;
    read(n);
    read(m);
    for(int i = 1;i <= n;i++){
        read(a[i]);
        f[i][0] = a[i];
    }
    for(int j = 1;j < 25;j++){
        for(int i = 1;i+(1<<j)-1 <= n;i++){
            f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    while(m--){
        int l,r;
        read(l);
        read(r);
        int len = r-l+1,ans = -1,be = l;
        for(int i = 0;len > 0;i++){
            if(len&1){
                ans = max(ans,f[be][i]);
                be += (1<<i);
            }
            len /= 2;
        }
        printf("%d\n",ans);
    }
    return 0;
}

但其实这个算法还可以再优化，如下（不想解释了，就主要用的是一个公式： $log(i) = log(i \div 2)+1$

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
int a[N],f[N][25],Log[N];
void read(int& x){
    x = 0;
    int f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-'){
            f = -1;
        }
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x *= 10;
        x += (c-'0');
        c = getchar();
    }
    x *= f;
}

int main(){
    // freopen("1.in","r",stdin);
    int n,m;
    read(n);
    read(m);
    for(int i = 1;i <= n;i++){
        read(a[i]);
        f[i][0] = a[i];
        if(i == 1){
            Log[i] = 0;
        } else{
            Log[i] = Log[(i/2)]+1;
        }
    }
    for(int j = 1;j < 25;j++){
        for(int i = 1;i+(1<<j)-1 <= n;i++){
            f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    while(m--){
        int l,r;
        read(l);
        read(r);
        int j = Log[(r-l+1)];
        printf("%d\n",max(f[l][j],f[r-(1<<j)+1][j]));
    }
    return 0;
}

Luogu P7809 [JRKSJ R2] 01 序列

我不太明白，还是等后续来扫尾吧

Luogu P8818 [CSP-S 2022] 策略游戏

我快明白了，但一个Bug快被整崩溃了，还是不够熟悉ST表，和AI对峙了两个多小时，愣是没有做出来

先把代码扔上来吧，别被我删了

#include<bits/stdc++.h>
#define LL long long

using namespace std;

const LL N = 1e5+10,B = 20;
LL a[N],b[N];
LL mxa[N][B],mxb[N][B],mna[N][B],mnb[N][B],fmx[N][B],zmn[N][B];
LL Log[N];

int main(){
//    freopen("1.in","r",stdin);
//    freopen("1.out","w",stdout);

    LL n,m,q;
    scanf("%lld%lld%lld",&n,&m,&q);
    Log[1] = 0;
    for(LL i = 2; i < N; i++){
        Log[i] = Log[i/2]+1;
    }
    for(LL i = 1;i <= n;i++){
        scanf("%lld",&a[i]);
    }
    for(LL j = 0;j < B;j++){
        for(LL i = 1;i <= n && i+(1<<j)-1 <= n;i++){
            if(j == 0){
                mxa[i][j] = a[i];
                mna[i][j] = a[i];
                fmx[i][j] = -1e18;
                zmn[i][j] = 1e18;
                if(a[i] < 0){
                    fmx[i][j] = a[i];
                } else{
                    zmn[i][j] = a[i];
                }
            } else{
                mxa[i][j] = max(mxa[i][j-1],mxa[i+(1<<(j-1))][j-1]);
                mna[i][j] = min(mna[i][j-1],mna[i+(1<<(j-1))][j-1]);
                fmx[i][j] = max(fmx[i][j-1],fmx[i+(1<<(j-1))][j-1]);
                zmn[i][j] = min(zmn[i][j-1],zmn[i+(1<<(j-1))][j-1]);  
            }
        }
    }

    for(LL i = 1;i <= m;i++){
        scanf("%lld",&b[i]);
    }
    for(LL j = 0;j < B;j++){
        for(LL i = 1;i <= m && i+(1<<j)-1 <= m;i++){
            if(j == 0){
                mxb[i][j] = b[i];
                mnb[i][j] = b[i];
            } else{
                mxb[i][j] = max(mxb[i][j-1],mxb[i+(1<<(j-1))][j-1]);
                mnb[i][j] = min(mnb[i][j-1],mnb[i+(1<<(j-1))][j-1]);
            }
        }
    }

    while(q--){
        LL l1,r1,l2,r2;
        LL ans;
        scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
        LL len1 = r1-l1+1,len2 = r2-l2+1;
        LL x = Log[len1],y = Log[len2];
        LL maxa = max(mxa[l1][x],mxa[r1-(1<<x)+1][x]);
        LL maxb = max(mxb[l2][y],mxb[r2-(1<<y)+1][y]);
        LL mina = min(mna[l1][x],mna[r1-(1<<x)+1][x]);
        LL minb = min(mnb[l2][y],mnb[r2-(1<<y)+1][y]);
        LL fmax = max(fmx[l1][x],fmx[r1-(1<<x)+1][x]);
        LL zmin = min(zmn[l1][x],zmn[r1-(1<<x)+1][x]);
        if((mina >= 0 && minb >= 0) || (maxa <= 0 || maxb <= 0)){
            if(mina >= 0){
                ans = 1ll*maxa*minb;
            } else{
                ans = 1ll*mina*maxb;
            }
        } else if((minb >= 0 || maxb <= 0) && (maxa >= 0 && mina <= 0)){
            if(minb >= 0){
                ans = 1ll*maxa*minb;
            } else{
                ans = 1ll*mina*maxb;
            }
        } else if((mina >= 0 && maxb <= 0) || (maxa <= 0 || minb >= 0)){
            if(mina >= 0){
                ans = 1ll*mina*minb;
            } else{
                ans = 1ll*maxa*maxb;
            }
        } else{
            ans = LLONG_MIN;
            if(fmax != -1e18){
                ans = max(ans,fmax*maxb);
            }
            if(zmin != 1e18){
                ans = max(ans,zmin*minb);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

（大样例没过)