【-70】P3865【模板】ST表[st表]

题目背景

这是一道ST表经典题——静态区间最大值

请注意最大数据时限只有0.8s,数据强度不低,请务必保证你的每次查询复杂度为 O(1)

题目描述

给定一个长度为 NN 的数列,和 MM 次询问,求出每一次询问的区间内数字的最大值。

输入输出格式

输入格式:

第一行包含两个整数 N, MN,M ,分别表示数列的长度和询问的个数。

第二行包含 NN 个整数(记为 a_iai),依次表示数列的第 ii 项。

接下来 MM行,每行包含两个整数 l_i, r_ili,ri,表示查询的区间为 [ l_i, r_i][li,ri]

输出格式:

输出包含 MM行,每行一个整数,依次表示每一次询问的结果。

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
9
10
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

输出样例#1:

1
2
3
4
5
6
7
8
9
9
7
7
9
8
7
9

说明

对于30%的数据,满足: $1 \leq N, M \leq 101≤N,M≤10$

对于70%的数据,满足:$ 1 \leq N, M \leq {10}^51≤N,M≤105$

对于100%的数据,满足: $ 1 \leq N \leq {10}^5, 1 \leq M \leq {10}^6, a_i \in [0, {10}^9], 1 \leq l_i \leq r_i \leq N $

题解

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
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int maxn=1e5+10;
int n,Q,x,y;
int a[maxn];
int f[maxn][21];//f[i][j]表示第i个数,往后2^j个数中的最大值(包括自己)
int ans;
int main()
{
n=read();Q=read();
for (register int i=1;i<=n;i++)
{
a[i]=read();f[i][0]=a[i];//读入+初始化
}
for (register int i=1;1<<i<=n;i++)
{
for (register int j=1;j<=n;j++)
{
if (j+(1<<i)>n+1) break;//超范围了
f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
//分成j~j+2^(i-1)和j+2^(i-1)~j+2^(i-1)+2^(i-1)
}
}
while (Q--)
{
x=read();y=read();
int s=0;
while (x+(1<<s)<=y) s++;s--;
ans=max(f[x][s],f[y-(1<<s)+1][s]);//x~y的最大值相当于这一部分的最大值
write(ans);//输出
printf("\n");
}
return 0;
}