Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给出n个数，m,k，问最大的j-i+1，使得【i,j】间的最大值与最小值的差属于[m,k] 思路：rmq+尺取。 2A.
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年05月19日 星期四 16时52分03秒
4File Name :code/hdu/3530.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34int n;
35int a[N];
36int dp[N][20],dp2[N][20];
37int m,k;
38
39void rmq_init()
40{
41 for ( int i = 1 ; i <= n ; i ++)
42 dp[i][0] = dp2[i][0] = a[i];
43
44 for ( int j = 1 ; (1<<j) <= n ; j++)
45 for ( int i = 1 ; i + (1<<j) -1 <= n ; i++)
46 {
47 dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
48 dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
49 }
50}
51
52int rmq( int l,int r)
53{
54 int k = 0 ;
55 while (1<<(k+1)<=r-l+1) k++;
56 int mx = max(dp[l][k],dp[r-(1<<k)+1][k]);
57 int mn = min(dp2[l][k],dp2[r-(1<<k)+1][k]);
58
59 return mx-mn;
60}
61
62int ruler()
63{
64 int head = 1;
65 int tail = 1;
66 int res = -1 ;
67 while (tail<=n)
68 {
69 int cur = rmq(head,tail);
70 while (head<tail&&rmq(head,tail)>k) head++;
71 while (tail<n&&rmq(head,tail)<m) tail++;
72 //if (tail>n) break;
73 cur = rmq(head,tail);
74 if (cur>=m&&cur<=k)
75 {
76 res = max(res,tail-head);
77 }
78// cout<<"head:"<<head<<" tail:"<<tail<<" cur:"<<cur<<" res:"<<res<<endl;
79 tail++;
80
81 }
82 return res+1;
83}
84int main()
85{
86 #ifndef ONLINE_JUDGE
87 freopen("code/in.txt","r",stdin);
88 #endif
89
90 while (scanf("%d %d %d",&n,&m,&k)!=EOF)
91 {
92 ms(dp,0);
93 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
94 if (m>k)
95 {
96 puts("0");
97 continue;
98 }
99 rmq_init();
100 printf("%d\n",ruler());
101 }
102
103
104
105 #ifndef ONLINE_JUDGE
106 fclose(stdin);
107 #endif
108 return 0;
109}