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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

/*
ST表
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
template<typename T>
void read(T& w)
{
	char r;int f=1;
	for(r=getchar();(r<48||r>57)&&r!='-';r=getchar());
	if(r=='-')r=getchar(),f=-1;
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
	w*=f;
}
const int maxn=int(1e5+3);
const int maxm=int(1e6+3);
int n,m;
int f[maxn][20];
int a[maxn];
void input()
{
	read(n),read(m);
	for(int i=1;i<=n;++i)
	{
		read(a[i]);
	}
}
void initF()
{
	for(int i=1;i<=n;++i)
	{
		f[i][0]=a[i];
	}
	for(int k=1;(1<<k)<=n;++k)
	{
		for(int i=1;i<=n;++i)
		{
			f[i][k]=f[i][k-1];
			if(i+(1<<(k-1))<=n&&f[i+(1<<(k-1))][k-1]>f[i][k])//caution! 下标可能越界
				f[i][k]=f[i+(1<<(k-1))][k-1];
		}
	}
}
int lg[maxn];
void initLG()
{
	lg[1]=0;
	lg[2]=1;
	for(int i=3;i<=n;++i)
	{
		lg[i]=lg[i/2]+1;
	}
}
int askmax(int l,int r)
{
	int len=r-l+1;
	int k=lg[len];
	return Max(f[l][k],f[r-(1<<k)+1][k]);
}
void solve()
{
	int l,r;
	for(int i=1;i<=m;++i)
	{
		read(l),read(r);
		printf("%d\n",askmax(l,r));
	}
}
int main()
{
	input();
	initLG();
	initF();
	solve();
	return 0;
} 

 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

//二维RMQ-正方形
int fm[maxn][maxn][8];
int fn[maxn][maxn][8];
void initMaxMin()
{
	for(int k=0;(1<<k)<=s;++k)
	{
		for(int i=1;i+(1<<(k))-1<=n;++i) for(int j=1;j+(1<<(k))-1<=m;++j)
		{
			if(k==0)
			{
				fm[i][j][0]=fn[i][j][0]=a[i][j];
			}
			else
			{
				fm[i][j][k]=
				Max(
					Max(
						fm[i][j][k-1],
						fm[i+(1<<(k-1))][j][k-1]),
					Max(
						fm[i][j+(1<<(k-1))][k-1],
						fm[i+(1<<(k-1))][j+(1<<(k-1))][k-1])
				);
				fn[i][j][k]=
				Min(
					Min(
						fn[i][j][k-1],
						fn[i+(1<<(k-1))][j][k-1]),
					Min(
						fn[i][j+(1<<(k-1))][k-1],
						fn[i+(1<<(k-1))][j+(1<<(k-1))][k-1])
				);
			}
		}
	}
}
int qMax(int ax,int ay,int bx,int by)
{
	int k=log2(bx-ax+1);
	return Max(
		Max(
			fm[ax][ay][k],
			fm[bx-(1<<k)+1][ay][k]),
		Max(
			fm[ax][by-(1<<k)+1][k],
			fm[bx-(1<<k)+1][by-(1<<k)+1][k])
	);
}
int qMin(int ax,int ay,int bx,int by)
{
	int k=log2(bx-ax+1);
	return Min(
		Min(
			fn[ax][ay][k],
			fn[bx-(1<<k)+1][ay][k]),
		Min(
			fn[ax][by-(1<<k)+1][k],
			fn[bx-(1<<k)+1][by-(1<<k)+1][k])
	);
}