洛谷3865 ST表

题面

原题

Solution

我们考虑ST表如何解决这道题目：
设\(dp[i][j]\)表示区间\(i\)~\(i+2^j-1\)的最值。
然后就考虑怎么转移？
\(dp[i][j]=max/min(dp[i][j-1],dp[i+(1<<j-1)][j-1])\)
然后就可以转移了！！

void RMQ_init(){
    for(int i=1;i<=n;i++)dp[i][0]=a[i];
    for(int j=1;j<=21;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]);
}

接着考虑如何求区间最值？直接套进去就好了！

int RMQ(int l,int r){
    int k=log2(r-l+1);
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}

所以说总结起来就是这样？

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#define ll long long
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
using namespace std;
inline int gi(){
    int sum=0,f=1;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return f*sum;
}
inline ll gl(){
    ll sum=0,f=1;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return f*sum;
}
const int maxn=100010;
int a[maxn],n,dp[maxn][32];
void RMQ_init(){
    for(int i=1;i<=n;i++)dp[i][0]=a[i];
    for(int j=1;j<=21;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]);
}
int RMQ(int l,int r){
    int k=log2(r-l+1);
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main(){
    int i,j,m,k,Q;
    n=gi();Q=gi();
    for(i=1;i<=n;i++)a[i]=gi();
    RMQ_init();
    while(Q--){
        int l=gi(),r=gi();
        printf("%d\n",RMQ(l,r));
    }
    return 0;
}

洛谷3865 ST表

原文：https://www.cnblogs.com/cjgjh/p/9819207.html