poj 3264（线段树 || ST(Sparse Table)算法）

Run ID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
10872456	xinghan0219	3264	Accepted	8540K	3469MS	G++	950B	2012-10-01 14:21:38
10579472	xinghan0219	3264	Accepted	1728K	3375MS	G++	1135B	2012-08-01 11:35:45

第一个是ST算法，第二个是线段树。

线段树:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 
 8 #define inf 100000000
 9 #define MAXN 50010
10 #define lson l,m,rt<<1
11 #define rson m+1,r,rt<<1|1
12 
13 
14 #define Max(x,y) ((x)>(y)?(x):(y))
15 #define Min(x,y) ((x)>(y)?(y):(x))
16 
17 int MAX[MAXN<<2];
18 int MIN[MAXN<<2];
19 
20 void PushUp(int rt)
21 {
22     MAX[rt] = Max(MAX[rt<<1],MAX[rt<<1|1]);
23     MIN[rt] = Min(MIN[rt<<1],MIN[rt<<1|1]);
24 }
25 
26 void build(int l,int r,int rt)
27 {
28     if(l==r)
29     {
30         scanf("%d",&MAX[rt]);
31         MIN[rt]=MAX[rt];
32         return;
33     }
34     int m=(r+l)>>1;
35     build(lson);
36     build(rson);
37     PushUp(rt);
38 }
39 int maxans=0,minans=inf;
40 
41 void query(int L,int R,int l,int r,int rt)
42 {
43     if(L <= l && r <=R)
44     {
45          maxans=Max(MAX[rt],maxans);
46          minans=Min(minans,MIN[rt]);
47          return ;
48     }
49     int m=(l+r)>>1;
50     //int ret
51     if(L <= m)
52         query(L,R,lson);
53     if(m<R)
54         query(L,R,rson);
55     return ;
56 }
57 
58 int main()
59 {
60     int n,q,l,r;
61     while(scanf("%d%d",&n,&q)!=EOF)
62     {
63         build(1,n,1);
64         while(q--)
65         {
66             scanf("%d%d",&l,&r);
67             maxans=0;
68             minans=inf;
69             query(l,r,1,n,1);
70             printf("%d\n",maxans-minans);
71         }
72     }
73     return 0;
74 }

ST:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 #define MAXN 50010
 9 #define Max(x,y) (x>y?x:y)
10 #define Min(x,y) (x>y?y:x)
11 
12 int maxsum[MAXN][20],minsum[MAXN][20];//
13 
14 void RMQ(int num)
15 {
16     for(int j=1;j<20;j++)
17         for(int i=1;i<=num;i++)
18         {
19             if(i+(1<<j)-1 <= num)
20             {
21                 maxsum[i][j]=Max(maxsum[i][j-1],maxsum[i+(1<<(j-1))][j-1]);
22                 minsum[i][j]=Min(minsum[i][j-1],minsum[i+(1<<(j-1))][j-1]);
23             }
24         }
25 }
26 
27 int main()
28 {
29     int i,j,num,t,query;
30     while(scanf("%d%d",&num,&query) != EOF)
31     {
32         for(i=1;i<=num;i++)
33         {
34             scanf("%d",&maxsum[i][0]);
35             minsum[i][0]=maxsum[i][0];
36         }
37         RMQ(num);
38         int st,en,maxl,minl;
39         while(query--)
40         {
41             scanf("%d%d",&st,&en);
42             int k=(int)((log(en-st+1))/log(2.0));
43             maxl=Max(maxsum[st][k],maxsum[en-(1<<k)+1][k]);
44             minl=Min(minsum[st][k],minsum[en-(1<<k)+1][k]);
45             printf("%d\n",maxl-minl);
46         }
47     }
48     return 0;
49 }

ps:ST算法可以将LCA问题转化成RMQ问题。。