hdu 3530 Subsequence (尺取+rmq)
题意:给出n个数,m,k,问最大的j-i+1,使得【i,j】间的最大值与最小值的差属于[m,k] 思路:rmq+尺取。 2A.
/* ***********************************************
Author :111qqz
Created Time :2016年05月19日 星期四 16时52分03秒
File Name :code/hdu/3530.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7int n;
8int a[N];
9int dp[N][20],dp2[N][20];
10int m,k;
1void rmq_init()
2{
3 for ( int i = 1 ; i <= n ; i ++)
4 dp[i][0] = dp2[i][0] = a[i];
1 for ( int j = 1 ; (1<<j) <= n ; j++)
2 for ( int i = 1 ; i + (1<<j) -1 <= n ; i++)
3 {
4 dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
5 dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
6 }
7}
1int rmq( int l,int r)
2{
3 int k = 0 ;
4 while (1<<(k+1)<=r-l+1) k++;
5 int mx = max(dp[l][k],dp[r-(1<<k)+1][k]);
6 int mn = min(dp2[l][k],dp2[r-(1<<k)+1][k]);
return mx-mn;
}
1int ruler()
2{
3 int head = 1;
4 int tail = 1;
5 int res = -1 ;
6 while (tail<=n)
7 {
8 int cur = rmq(head,tail);
9 while (head<tail&&rmq(head,tail)>k) head++;
10 while (tail<n&&rmq(head,tail)<m) tail++;
11 //if (tail>n) break;
12 cur = rmq(head,tail);
13 if (cur>=m&&cur<=k)
14 {
15 res = max(res,tail-head);
16 }
17// cout<<"head:"<<head<<" tail:"<<tail<<" cur:"<<cur<<" res:"<<res<<endl;
18 tail++;
1 }
2 return res+1;
3}
4int main()
5{
6 #ifndef ONLINE_JUDGE
7 freopen("code/in.txt","r",stdin);
8 #endif
1 while (scanf("%d %d %d",&n,&m,&k)!=EOF)
2 {
3 ms(dp,0);
4 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
5 if (m>k)
6 {
7 puts("0");
8 continue;
9 }
10 rmq_init();
11 printf("%d\n",ruler());
12 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}