poj3264Balanced Lineup(线段树RMQ）

RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。

1A 程序跑的好慢 3000+

输完更新父节点的最小最大值找的时候找两次一次最大一次最小相减

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 using namespace std;
 5 #define N 50001
 6 #define MAX 1000001
 7 int s[N*4],mi[N*4],ma[N*4];
 8 void upset(int l,int r,int w)
 9 {
10     if(l==r)
11     return ;
12     int m = (l+r)/2;
13     upset(l,m,2*w);
14     upset(m+1,r,2*w+1);
15     mi[w] = min(mi[w*2],mi[2*w+1]);
16     ma[w] = max(ma[w*2],ma[2*w+1]);
17 }
18 void build(int l,int r,int w)
19 {
20     if(l==r)
21     {
22         scanf("%d", &s[w]);
23         mi[w] = s[w];
24         ma[w] = s[w];
25         return ;
26     }
27     int m = (l+r)/2;
28     build(l,m,2*w);
29     build(m+1,r,2*w+1);
30 }
31 int search(int a,int b,int l,int r,int w)
32 {
33     if(a==l&&b==r)
34     return mi[w];
35     int m = (l+r)/2,re = MAX;
36     if(b<=m)
37     re = min(re,search(a,b,l,m,2*w));
38     else
39     if(a>m)
40     re = min(re,search(a,b,m+1,r,2*w+1));
41     else
42     {
43         re = min(re,search(a,m,l,m,2*w));
44         re = min(re,search(m+1,b,m+1,r,2*w+1));
45     }
46     return re;
47 }
48 int search1(int a,int b,int l,int r,int w)
49 {
50     if(a==l&&b==r)
51     {
52         return ma[w];
53     }
54     int m = (l+r)/2,re = -1;
55     if(b<=m)
56     re = max(re,search1(a,b,l,m,2*w));
57     else
58     if(a>m)
59     re = max(re,search1(a,b,m+1,r,2*w+1));
60     else
61     {
62         re = max(re,search1(a,m,l,m,2*w));
63         re = max(re,search1(m+1,b,m+1,r,2*w+1));
64     }
65     return re;
66 }
67 int main()
68 {
69     int n,q,i,j,k,a,b;
70     while(scanf("%d%d", &n,&q)!=EOF)
71     {
72         build(1,n,1);
73         upset(1,n,1);
74         while(q--)
75         {
76             scanf("%d%d", &a,&b);
77             printf("%d\n",search1(a,b,1,n,1)-search(a,b,1,n,1));
78         }
79     }
80     return 0;
81 }