AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

st板子

作者: 作者的头像   leimingze ,  2022-11-23 19:00:35 ,  所有人可见 ,  阅读 175


2


const int N=2e5+10,M=log2(N);
int a[N];
int f[2][N][M];
void st()
{
    for(int j=0;(1<<j)<=n;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
            if(!j)f[0][i][j]=f[1][i][j]=a[i];
            else 
            {
                f[0][i][j]=max(f[0][i][j-1],f[0][i+(1<<(j-1))][j-1]);
                f[1][i][j]=min(f[1][i][j-1],f[1][i+(1<<(j-1))][j-1]);
            }
    }
}
int query(int l,int r,bool s)
{
    int len=r-l+1;
    int q=log2(len);
    if(s)return max(f[0][l][q],f[0][r-((1<<q)-1)][q]);
    else return min(f[1][l][q],f[1][r-((1<<q)-1)][q]);
}

0 评论

你确定删除吗?

© 2018-2023 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息