poj3264Balanced Lineup

查找区间最值，做差。

 1 #include<cstdio>
 2 #include<iostream>
 3 #define lson l,m,rt<<1
 4 #define rson m+1,r,rt<<1|1
 5 #define ll long long
 6 using namespace std;
 7 const int maxn=50010;
 8 int f[maxn<<2];
 9 int k[maxn<<2];
10 
11 inline void pushup(int rt)
12 {
13     f[rt]=max(f[rt<<1],f[rt<<1|1]);
14     k[rt]=min(k[rt<<1],k[rt<<1|1]);
15 }
16 
17 void build(int l,int r,int rt)
18 {
19     if(l==r)
20     {
21         scanf("%lld",&f[rt]);
22         k[rt]=f[rt];
23         return;
24     }
25     int m=(l+r)>>1;
26     build(lson);
27     build(rson);
28     pushup(rt);
29 }
30 
31 int querymax(int L,int R,int l,int r,int rt)
32 {
33     if(L<=l&&r<=R) return f[rt];
34     int m=(l+r)>>1;
35     int ans=-1;
36     if(L<=m) ans=max(ans,querymax(L,R,lson));
37     if(m<R) ans=max(ans,querymax(L,R,rson));
38     return ans;
39 }
40 int querymin(int L,int R,int l,int r,int rt)
41 {
42     if(L<=l&&r<=R) return k[rt];
43     int m=(l+r)>>1;
44     int ans=99999999999;  
45     if(L<=m) ans=min(ans,querymin(L,R,lson));
46     if(m<R) ans=min(ans,querymin(L,R,rson));
47     return ans;
48 }
49 int main()
50 {
51     int n,m;
52     while(scanf("%d%d",&n,&m)!=EOF)
53     {
54         build(1,n,1);
55         while(m--)
56         {
57             int a,b;
58             scanf("%d%d",&a,&b);
59             int M=querymax(a,b,1,n,1);
60             int mm=querymin(a,b,1,n,1);
61             printf("%d
",M-mm);
62         }
63     }
64 }

刚学了RMQ，方便很多。。。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 const int maxn=500010;
 7 
 8 int maxx[maxn][25],minn[maxn][25];
 9 int a[maxn];
10 int n,m;
11 void RMQ_INIT(int n)
12 {
13     int k=log(n+0.0)/log(2.0);
14     for(int i=0;i<n;i++)
15     {
16         maxx[i][0]=a[i];
17         minn[i][0]=a[i];
18     }
19     for(int j=1;j<=k;j++)
20         for(int i=0;i+(1<<j)-1<n;i++)
21     {
22         maxx[i][j]=max(maxx[i][j-1],maxx[i+(1<<j-1)][j-1]);
23         minn[i][j]=min(minn[i][j-1],minn[i+(1<<j-1)][j-1]);
24     }
25     return ;
26 }
27 int rmq(int x,int y)
28 {
29     int k=log(y*1.0-x+1)/log(2.0);
30     int a=max(maxx[x][k],maxx[y-(1<<k)+1][k]);
31     int b=min(minn[x][k],minn[y-(1<<k)+1][k]);
32     return a-b;
33 }
34 int main()
35 {
36     while(scanf("%d%d",&n,&m)!=EOF)
37     {
38         for(int i=0;i<n;i++)
39             scanf("%d",&a[i]);
40         RMQ_INIT(n);
41         while(m--)
42         {
43             int u,v;
44             scanf("%d%d",&u,&v);
45             u--;
46             v--;
47             printf("%d
",rmq(u,v));
48         }
49     }
50 }