BZOJ 1342 Baltic2007 Sound静音问题 单调队列

题目大意：给定一个长度为n的序列，求哪些长度为m的区间满足区间内最大值与最小值之差小于等于c

利用单调队列维护区间内的最大值和最小值- - 硬搞就可以了- -

刷刷水题真爽- -

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define M 1001001 using namespace std; int n,m,c,a[M]; int q_max[M],r_max,h_max; int q_min[M],r_min,h_min; bool flag; int main() { int i; cin>>n>>m>>c; for(i=1;i<=n;i++) { scanf("%d",&a[i]); { int &r=r_max,&h=h_max,*q=q_max; while( r-h>=1 && a[q[r]]
      
       =m) q[++h]=0; } { int &r=r_min,&h=h_min,*q=q_min; while( r-h>=1 && a[q[r]]>a[i] ) q[r--]=0; q[++r]=i; while(i-q[h+1]>=m) q[++h]=0; } if( i>=m && a[q_max[h_max+1]]-a[q_min[h_min+1]]<=c ) printf("%d\n",i-m+1),flag=1; } if(!flag) puts("NONE"); return 0; }