Akira的OI(咸鱼)圈

ST表

Word count: 314 / Reading time: 2 min
2018/08/17 Share

我们以查询静态区间最大值为例,f[i][j]中的i表示区间起始点为i、j表示区间长度为2^j,f[i][j]的值即为i~i+2^j-1的区间最大值。由比较f[l][lg[r-l+1]]与f[r-lg[r-l+1]+1][lg[r-l+1]]大小(lg[r-l+1]会向下取整)即可得到区间[l,r]最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define maxn 1000001
using namespace std;
inline int read()
{
int l=0,w=1;
char ch=0;
while(ch<'0'||ch>'9')
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
l=(l<<3)+(l<<1)+(ch^'0');
ch=getchar();
}
return w*l;
}
int n,f[maxn][18],lg[maxn];
inline int query(int l,int r)
{
int t=lg[r-l+1];
return max(f[l][t],f[r-(1<<t)+1][t]);
}
int main()
{
int m,x,y;
n=read(),m=read();
for(int i=2;i<=n;i++)
lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++)
f[i][0]=read();
for(int j=1;j<18;j++)
for(int i=1;i<=n-(1<<j-1);i++)
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
while(m--)
{
x=read(),y=read();
printf("%d\n",query(x,y));
}
return 0;
}

CATALOG