hdu 3530 Subsequence 单调队列 求最长连续区间,满足条件（m<=max-min<=k)

Subsequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 734    Accepted Submission(s): 277

Problem Description There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k.  

Input There are multiple test cases.

For each test case, the first line has three integers, n, m and k. n is the length of the sequence and is in the range [1, 100000]. m and k are in the range [0, 1000000]. The second line has n integers, which are all in the range [0, 1000000].

Proceed to the end of file.

Output For each test case, print the length of the subsequence on a single line.  

Sample Input

5 0 0
1 1 1 1 1
5 0 3
1 2 3 4 5
        

Sample Output

5
4
  
  
   #include<iostream>
   
#include<cstdio>
   
#include<cstring>
   
using namespace std;
   
int f[100005],p[100005],q[100005],p1,p2,q1,q2,now,n,m,k,i,ans;
   
int main()
   
{
   
 while(scanf("%d%d%d",&n,&m,&k)==3)
   
 {
   
     memset(p,0,sizeof(p));
   
     memset(q,0,sizeof(q));
   
  p1=q1=q2=p2=now=ans=0;
   
  for (i=0;i<n;i++) scanf("%d",&f[i]);
   
  for (i=0;i<n;i++)
   
  {
   
   while(p2>=1&&f[i]<=f[p[p2-1]]&&p1<p2) p2--;p[p2++]=i;
   
   while(q2>=1&&f[i]>=f[q[q2-1]]&&q1<q2) q2--;q[q2++]=i;
   
   while(f[q[q1]]-f[p[p1]]>k) if (p[p1]<q[q1]) {now=p[p1]+1;p1++;}else {now=q[q1]+1;q1++;}
   
   if (f[q[q1]]-f[p[p1]]<=k&&f[q[q1]]-f[p[p1]]>=m) if (i-now+1>ans) ans=i-now+1;
   
  }
   
  printf("%d/n",ans);
   
 }
   
}
  
  
   

  
  
   #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100005;
int Q_max[maxn],I_max[maxn];
int Q_min[maxn],I_min[maxn];
int a[maxn];
int main()
{
    int n,m,k;
    while(scanf("%d%d%d",&n,&m,&k)==3)
    {
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        int head_max=0,tail_max=-1;
        int head_min=0,tail_min=-1;
        int now=1;
        int _max=0;
        for(int i=1;i<=n;i++)
        {
            //a[i]入队
            while(head_max<=tail_max&&Q_max[tail_max]<=a[i]) tail_max--;
            while(head_min<=tail_min&&Q_min[tail_min]>=a[i]) tail_min--;
            tail_max++;Q_max[tail_max]=a[i],I_max[tail_max]=i;
            tail_min++;Q_min[tail_min]=a[i],I_min[tail_min]=i;
            while(Q_max[head_max]-Q_min[head_min]>k)
            {
                if(I_max[head_max]>I_min[head_min]) now=I_min[head_min]+1,head_min++;
                else now=I_max[head_max]+1,head_max++;
            }
            if(Q_max[head_max]-Q_min[head_min]>=m&&Q_max[head_max]-Q_min[head_min]<=k)
            {
                if(i-now+1>_max) _max=i-now+1;
            }
        }
        printf("%d/n",_max);
    }
    return 0;
}