xfstart07
Get busy living or get busy dying
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 阅读(228) 评论(0)  编辑 收藏 引用 所属分类: 算法学习竞赛题库PKU数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理