题解 P3865 【【模板】ST表】
hicc0305
2017-08-08 18:53:12
竟然没有人写题解= =，这题做的人也太少了= =
裸ST求RMQ（毕竟是模板题）
用f[i][j]表示j—(j+2^i-1)中的最大值
于是dp转移方程就是f[i][j]=max(f[i-1][j],f[i-1][j+(1<<(i-1))])
然后o(1)处理出每个询问：把l~r分成两块，取最大值，两块分别是f[k][l],f[k][r-(1<<k)+1]) （k=log2(j-i+1)）
总共的复杂度是O(nlogn)+O(m)
上代码！！！
```cpp
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int a[100001];
int f[20][100001];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
f[0][i]=a[i];//初始化，每个点的包括自己的后2^0个就是它自己
for(int i=1;i<=log(n)/log(2);i++)
for(int j=1;j<=n-(1<<i)+1;j++)
f[i][j]=max(f[i-1][j],f[i-1][j+(1<<(i-1))]);//dp转移不解释
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
int k=log(r-l+1)/log(2);//就是log2(j-i+1)
printf("%d\n",max(f[k][l],f[k][r-(1<<k)+1]));//分成两个区间求最大不解释，用cout的童鞋们别被坑了，会T的= =
}
return 0;
}
```