BZOJ 2096([Poi2010]Pilots-單調隊列-差值)

2096: [Poi2010]Pilots
Time Limit: 30 Sec  Memory Limit: 162 MB
Submit: 190  Solved: 97
[Submit][Status]
Description
Tz又耍畸形了！！他要當飛行員，他拿到了一個飛行員測試難度序列，他設定了一個難度差的最大值，在序列中他想找到一個最長的子串，任意兩個難度差不會超過他設定的最大值。耍畸形一個人是不行的，於是他找到了你。
Input
輸入：第一行兩個有空格隔開的整數k（0<=k<=2000,000,000），n(1<=n<=3000,000)，k代表Tz設定的最大值，n代表難度序列的長度。第二行為n個由空格隔開的整數ai（1<=ai<=2000,000,000），表示難度序列。
Output
輸出：最大的字串長度。
Sample Input
3 9
5 1 3 5 8 6 6 9 10
Sample Output
4
（有兩個子串的長度為4: 5, 8, 6, 6 和8, 6, 6, 9.最長子串的長度就是4）

HINT

Source
by poi

對，沒錯就是單調隊列。

我第一次用priority_queue實現單調隊列（其實差不多）

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
#include<cassert>
#include<climits>
#include<queue>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define F (1000000009)
#define MAXN (3000000+10)
#define MAXK (2000000000)
typedef long long ll;
int n;
ll k,a[MAXN];
struct node
{
   int v,i;
   node(){}
   node(int _i,int _v):v(_v),i(_i){}
   friend bool operator<(node a,node b){return a.v<b.v;};
};
priority_queue<node> h1,h2;
int main()
{
// freopen("bzoj2096.in","r",stdin);
   cin>>k>>n;
   int l=1,ans=0;
   For(i,n) 
   {
      scanf("%lld",&a[i]);
      h1.push(node(i,a[i])),h2.push(node(i,-a[i]));
      while (h1.top().v+h2.top().v>k)
      {
         l++;
         while (!h1.empty()&&h1.top().i<l) h1.pop(); 
         while (!h2.empty()&&h2.top().i<l) h2.pop(); 
      }
      ans=max(ans,i-l+1);
      
//      cout<<h1.top()<<' '<<h2.top()<<endl;
   }
   cout<<ans<<endl;
   
//   while(1);
   return 0;
}