CSU1553 Good subsequence —— 二分 + RMQ/线段树

题目链接： http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1553

Description

Give you a sequence of n numbers, and a number k you should find the max length of Good subsequence. Good subsequence is a continuous subsequence of the given sequence and its maximum value - minimum value<=k. For example n=5, k=2, the sequence ={5, 4, 2, 3, 1}. The answer is 3, the good subsequence are {4, 2, 3} or {2, 3, 1}.

Input

There are several test cases.
Each test case contains two line. the first line are two numbers indicates n and k (1<=n<=10,000, 1<=k<=1,000,000,000). The second line give the sequence of n numbers a[i] (1<=i<=n, 1<=a[i]<=1,000,000,000).
The input will finish with the end of file.

Output

For each the case, output one integer indicates the answer.

Sample Input

Sample Output

3
1

题解：

之前学了RMQ，线段树，树状数组，但是一直不知道他们在哪里能派上用场。通过这题，终于找到他们的用武之地了：区间查询最大最小值。

解决了查询区间最大最小值的问题，剩下的就是二分了。这里是二分长度。

RMQ：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <vector>
 7 #include <map>
 8 #include <set>
 9 #include <queue>
10 #include <sstream>
11 #include <algorithm>
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define ms(a, b)  memset((a), (b), sizeof(a))
16 //#define LOCAL
17 #define eps 0.0000001
18 #define LNF (1<<60)
19 typedef long long LL;
20 const int inf = 0x3f3f3f3f;
21 const int maxn = 10000+10;
22 const int mod = 1e9+7;
23 
24 LL st_max[maxn][16], st_min[maxn][16];
25 LL a[maxn];
26 
27 void RMQ_init(int n)
28 {
29     for(int i = 0; i<n; i++)
30     {
31         st_min[i][0] = a[i];
32         st_max[i][0] = a[i];
33     }
34 
35     for(int j = 1; (1<<j)<=n; j++)//枚举长度
36     for(int i = 0; i+(1<<j)-1<n; i++)//枚举起点
37     {
38         st_min[i][j] = min(st_min[i][j-1],st_min[i+(1<<(j-1))][j-1]);
39         st_max[i][j] = max(st_max[i][j-1],st_max[i+(1<<(j-1))][j-1]);
40     }
41 }
42 
43 LL RMQ(int l, int r)//查询
44 {
45     int k = 0;
46     while((1<<(k+1))<=r-l+1)
47         k++;
48     return max(st_max[l][k],st_max[r-(1<<k)+1][k]) - min(st_min[l][k],st_min[r-(1<<k)+1][k]);
49 }
50 
51 int test(int len, int n, int k)
52 {
53     for(int i = len-1; i<n; i++)
54         if(RMQ(i-len+1, i)<=1LL*k)
55             return 1;
56 
57     return 0;
58 }
59 
60 int main()
61 {
62 #ifdef LOCAL
63     freopen("input.txt", "r", stdin);
64 //      freopen("output.txt", "w", stdout);
65 #endif // LOCAL
66 
67     int n, k;
68     while(~scanf("%d%d", &n, &k))
69     {
70         for(int i=0;i<n;i++)
71             scanf("%lld", &a[i]);
72 
73         ms(st_max, 0);
74         ms(st_min, 0);
75         RMQ_init(n);
76 
77         int l = 1, r = n;
78         while(l<=r)
79         {
80             int mid = (l+r)/2;
81             if(test(mid, n, k))
82                 l = mid+1;
83             else
84                 r = mid-1;
85         }
86         printf("%d
", r);
87     }
88     return 0;
89 }

View Code

线段树：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <vector>
 7 #include <map>
 8 #include <set>
 9 #include <queue>
10 #include <sstream>
11 #include <algorithm>
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define ms(a, b)  memset((a), (b), sizeof(a))
16 //#define LOCAL
17 #define eps 0.0000001
18 #define LNF 1000000000000
19 typedef long long LL;
20 const int inf = 0x3f3f3f3f;
21 const int maxn = 10000+10;
22 const int mod = 1e9+7;
23 
24 LL st_max[4*maxn], st_min[4*maxn];
25 LL a[maxn];
26 
27 void build(int rt, int l, int r)
28 {
29     if(l==r)
30     {
31         st_max[rt] = a[r];
32         st_min[rt] = a[r];
33         return;
34     }
35 
36     int mid = (l+r)>>1;
37     build(rt*2,l,mid);
38     build(rt*2+1,mid+1,r);
39     st_max[rt] = max(st_max[rt*2], st_max[rt*2+1]);
40     st_min[rt] = min(st_min[rt*2], st_min[rt*2+1]);
41 }
42 
43 //由于最大最小值都要查询，而return只能返回一个，所以用ma和mi记录最小值
44 LL query(int rt, int l, int r, int x, int y, LL &ma, LL &mi)
45 {
46     if(x<=l && y>=r)
47     {
48         ma = max(ma,st_max[rt]);
49         mi = min(mi,st_min[rt]);
50         return ma - mi;
51     }
52 
53     int mid = (l+r)>>1;
54     if(y<=mid) query(rt*2,l,mid,x,y,ma,mi);
55     else if(x>=mid+1) query(rt*2+1,mid+1,r,x,y,ma,mi);
56     else query(rt*2,l,mid,x,mid,ma,mi),query(rt*2+1,mid+1,r,mid+1,y,ma,mi);
57 
58     return ma - mi;
59 }
60 
61 int test(int len, int n, int k)
62 {
63     for(int i = len-1; i<n; i++)
64     {
65         LL ma = -LNF, mi = LNF;
66         if(query(1,0,n-1, i-len+1, i, ma,mi)<=1LL*k)
67             return 1;
68     }
69     return 0;
70 }
71 
72 int main()
73 {
74 #ifdef LOCAL
75     freopen("input.txt", "r", stdin);
76 //      freopen("output.txt", "w", stdout);
77 #endif // LOCAL
78 
79     int n, k;
80     while(scanf("%d%d", &n, &k)!=EOF)
81     {
82         for(int i=0;i<n;i++)
83             scanf("%lld", &a[i]);
84 
85         build(1,0,n-1);
86 
87         int l = 1, r = n;
88         while(l<=r)
89         {
90             int mid = (l+r)/2;
91             if(test(mid, n,k))
92                 l = mid+1;
93             else
94                 r = mid-1;
95         }
96         printf("%d
", r);
97     }
98     return 0;
99 }

View Code