RMQ问题
题目大意：给出一个数列，在给出一系列询问，（a，b）查询a到b之间最大值-最小值。
解法一：线段树
1 /*
2 * Problem: USACO 2007 January Silver-lineupg PKU 3264
3 * Author: Xu Fei
4 * Time: 2010.8.13 16:21
5 * Method: 线段树
6 */
7 #include<iostream>
8 #include<cstdio>
9 using namespace std;
10
11 const int MaxN=50001,INF=0xFFFFFFF;
12
13 struct Node
14 {
15 int a,b,ma,mi;
16 }tree[MaxN*4];
17 int N,Q;
18 int A[MaxN];
19 int Max,Min;
20
21 inline int max(int a,int b) { return a>b?a:b; }
22 inline int min(int a,int b) { return a<b?a:b; }
23
24 void build(int num,int l,int r)
25 {
26 tree[num].a=l;
27 tree[num].b=r;
28 tree[num].ma=-INF;
29 tree[num].mi=INF;
30 if(l<r)
31 {
32 int mid=(l+r)>>1;
33 build(num<<1,l,mid);
34 build((num<<1)+1,mid+1,r);
35 tree[num].ma=max(tree[num<<1].ma,tree[(num<<1)+1].ma);
36 tree[num].mi=min(tree[num<<1].mi,tree[(num<<1)+1].mi);
37 }
38 else
39 {
40 tree[num].ma=A[l];
41 tree[num].mi=A[l];
42 }
43 }
44 void query(int num,int l,int r)
45 {
46 if(tree[num].a == l && tree[num].b == r)
47 {
48 Max=max(Max,tree[num].ma);
49 Min=min(Min,tree[num].mi);
50 return;
51 }
52 int mid=(tree[num].a+tree[num].b)>>1;
53 if(r <= mid)
54 query(num<<1,l,r);
55 else if(l > mid)
56 query((num<<1)+1,l,r);
57 else
58 {
59 query(num<<1,l,mid);
60 query((num<<1)+1,mid+1,r);
61 }
62 }
63 int main()
64 {
65 freopen("lineupg.in","r",stdin);
66 freopen("lineupg.out","w",stdout);
67 int i,a,b;
68 scanf("%d%d",&N,&Q);
69 for(i=1;i<=N;++i)
70 scanf("%d",A+i);
71 build(1,1,N);
72 for(i=1;i<=Q;++i)
73 {
74 scanf("%d%d",&a,&b);
75 Max=-INF; Min=INF;
76 query(1,a,b);
77 printf("%d\n",Max-Min);
78 }
79 return 0;
80 }
81
解法二：ST算法
DD牛解析：
另一种算法就是神奇的ST算法（Sparse Table）
，以求最大值为例，设v[n][f]表示[n,n+2^f)这个区间内的最大值，那么在询问到[a,b)区间的最大值时答案就是max(v[a]
[f],v[b-2^f][f])，其中f是满足2^f<=b-a的最大的f。至于那张稀疏表，可以用递推的方法在O(nlogn)（也就是表的元
素数）的时间内构建。也就是说v[n][f]=max(v[n][f-1],v[n+2^(f-1)][f])。
1 /*
2 * Problem: USACO 2007 January Silver-lineupg PKU 3264
3 * Author: Xu Fei
4 * Time: 2010.8.12 15:38
5 * Method: ST算法
6 */
7 #include<iostream>
8 #include<cstdio>
9 using namespace std;
10
11 const int MaxN=50010,MaxM=17;
12
13 int N,Q;
14 int A1[MaxN][MaxM];
15 int A2[MaxN][MaxM];
16
17 inline int max(int a,int b){ return a>b?a:b; }
18 inline int min(int a,int b){ return a<b?a:b; }
19
20 int main()
21 {
22 freopen("lineupg.in","r",stdin);
23 freopen("lineupg.out","w",stdout);
24 int i,j,n,a,b,p;
25 scanf("%d%d",&N,&Q);
26 for(i=0;i<N;++i)
27 {
28 scanf("%d",&A1[i][0]);
29 A2[i][0]=A1[i][0];
30 }
31 for(i=1,j=1;j<N;++i)
32 {
33 for(n=0;;++n)
34 {
35 if(n+j>=N)
36 break;
37 A1[n][i]=max(A1[n][i-1],A1[n+j][i-1]);
38 A2[n][i]=min(A2[n][i-1],A2[n+j][i-1]);
39 }
40 j=1<<i;
41 }
42 for(i=0;i<Q;++i)
43 {
44 scanf("%d%d",&a,&b);
45 --a;
46 p=b-a;
47 for(j=0;(1<<j)<=p;++j);
48 --j;
49 printf("%d\n",max(A1[a][j],A1[b-(1<<j)][j])-
50 min(A2[a][j],A2[b-(1<<j)][j]));
51 }
52 return 0;
53 }
54
posted on 2010-08-12 15:38
xfstart07 阅读(238)
评论(0) 编辑 收藏 引用 所属分类:
算法学习 、
竞赛题库 、
PKU 、
数据结构