题解 P2880 【[USACO07JAN]平衡的阵容Balanced Lineup】

发表于 | 更新于 | 阅读次数：

ST表详解

点了最短路的标签出了这题…
好吧一看就知道是用ST表，也想过用线段树，不过显然ST表更优秀。

我就先详讲ST的原理

我们先讲讲ST表是什么。

ST表是利用一种倍增的思想，也算是动态规划？

我们用一个二维数组st1 [ i ] [ j ] 表示以i为起点向右$ 2^j $的区间的最大值，

用一个二维数组st2 [ i ] [ j ]表示以i为起点向右$ 2^j $的区间的最小值。

那么我们来想怎么转移，对于一个区间像下面这样

st1 [ i ] [ j ]可以从 i~i+$ 2^{j-1} $和i+$ 2^{j-1} $~i+$ 2^j $转移过来，

st2也是一样的，只不过是取最大最小罢了。

讲完了制表，我们来讲讲怎么查询，我们要用到一个炒鸡好用的函数———>$ log_2 $

对于要查询的区间l,r，有可能（l-r）不是2的幂次，那么我们就需要合并
这样子的两个区间

那么我们就直接合并这个红色和绿色的区间，有些小天才可能会有疑问，
比如，这个重叠部分会有影响，答案是

完全没有

因为最大最小值是支持结合律的，那么我们也可以从这里推出ST表的一个性质，

ST表支持结合律的区间查询问题。

接下来就是快乐的代码时间

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
83
84
#include<bits/stdc++.h>
#define swap mswap
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)//手写据说常数小（大雾）
using namespace std;
void swap(int &x,int &y)
{
	x^=y^=x^=y;
}
void read(int &x)
{
	x=0;
	char ch=getchar();
	int pd=1;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		{
			pd=-pd;
		}
		ch=getchar();
	}
	while(ch<='9'&&ch>='0')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=pd;
}
void write(const int &x)
{
	char f[100001];
	int s=0;
	int tmp=x;
	if(tmp==0)
	{
		putchar('0');
		return;
	}
	if(tmp<0)
	{
		tmp=-tmp;
		putchar('-');
	}
	while(tmp>0)
	{
		f[s++]=tmp%10+'0';
		tmp/=10;
	}
	while(s>0)
	{
		putchar(f[--s]);
	}
}
const int N=5e4+10;
int n,m,a[N],st1[N][21],st2[N][21];
int main()
{
	memset(st2,60,sizeof(st2));//最小值注意赋无穷大
	read(n);
	read(m);
	for(register int i=1;i<=n;++i)
	{
		read(a[i]);
		st1[i][0]=st2[i][0]=a[i];
	}
	for(register int j=1;j<=21;++j)
	{
		for(register int i=1;(i+(1<<j-1))<=n;++i)
		{
			st1[i][j]=max(st1[i][j-1],st1[i+(1<<j-1)][j-1]);st1记录区间最大值
			st2[i][j]=min(st2[i][j-1],st2[i+(1<<j-1)][j-1]);st2最小值
		}
	}
	for(register int i=1;i<=m;++i)
	{
		int l,r;
		read(l);
		read(r);
		int k=log2(r-l+1);//+1防止RE？（雾）
		write(max(st1[l][k],st1[r-(1<<k)+1][k])-min(st2[l][k],st2[r-(1<<k)+1][k]));;
		puts("");
	}
}