首页 > 其他 > 详细

st表模板

时间:2020-01-27 22:58:25      阅读:113      评论:0      收藏:0      [点我收藏+]

一.st取区间最大值

     模板题洛谷P3865:https://www.luogu.com.cn/problem/P3865

注意点:

1.f[i][j]=f[i][i+2j-1] 

2.预处理时是以2的次幂进行跳的取区间最大值

技术分享图片

 

 

 

3.Q询问函数:

询问时取的len的方法是由:2x<=r-l+1来取的,由于不是等于号所以f[i][j-1],f[i+(1<<(j-1))][j-1]一定是包含了整个区间的,只是可能有重复贡献问题,但是由于是取最大值,所以重复贡献并不影响结果

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int lgn=21;取法是总值的2lgn
int f[maxn][lgn];

void st()
{
    for(int j=1; j<=lgn; ++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]);
}
int Q(int l,int r)
{
    int len=log(r-l+1)/log(2);
    return max(f[l][len],f[r-(1<<len)+1][len]);
}

int main()
{
    int n,m;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; ++i)
        cin>>f[i][0];
    for(int i=1; i<=m; ++i)
    {
        int l,r;
        cin>>l>>r;
        cout<<Q(l,r)<<endl;
    }
    return 0;
}

 

st表模板

原文:https://www.cnblogs.com/waryan/p/12237061.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!