st板子
作者:
leimingze
,
2022-11-23 19:00:35
,
所有人可见
,
阅读 175
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]);
}