hdu 5289 rmp+二分+枚举后界 or单调队列 ****

好题~~

给你n个数和k，求有多少的区间使得区间内部任意两个数的差值小于k，输出符合要求的区间个数，枚举后界~~

又是一种没见过的方法，太弱了/(ㄒoㄒ)/~~

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <iostream>

 #include <queue>

 #include <algorithm>

 #include <vector>

 #include <set>

 using namespace std;

 #define LL __int64

 #define INF 0x3f3f3f3f

 const int MAXN=;

 #define mod 1000000007

 int a[MAXN];

 LL ans;

 int dp1[MAXN][],dp2[MAXN][];

 void init(int n)

 {

     for(int i=;i<=n;i++)

         dp1[i][]=dp2[i][]=a[i];

     for(int j=;(<<j)<=n;j++)

     {

         for(int i=;i+(<<j)-<=n;i++)

         {

             dp1[i][j]=max(dp1[i][j-],dp1[i+(<<(j-))][j-]);

             dp2[i][j]=min(dp2[i][j-],dp2[i+(<<(j-))][j-]);

         }

     }

 }

 int RMQ(int L,int R)

 {

     int k=;

     while((<<(k+))<=R-L+)k++;

     return max(dp1[L][k],dp1[R-(<<k)+][k])-min(dp2[L][k],dp2[R-(<<k)+][k]);

 }

 int binarySearch(int L,int R,int n,int k)

 {

     int mid;

     int l=L,r=R;

     while(l<=r)

     {

         mid=(l+r)/;

         if(RMQ(mid,R)>=k)

         {

             l=mid+;

         }

         else

         {

             r=mid-;

         }

     }

     if(RMQ(mid,R)>=k)

         mid++;

     return mid;

 }

 int main()

 {

     int T,i,j,n,k,mi,ma,l,r;

     while(~scanf("%d",&T))

     {

         while(T--)

         {

             scanf("%d%d",&n,&k);

             for(i=;i<=n;i++)

                 scanf("%d",&a[i]);

             if(!k)

             {

                 printf("0\n");

                 continue;

             }

             if(k==)

             {

                 printf("%d\n",n);

                 continue;

             }

             init(n);

             ans=;

             for(i=j=;i<=n;i++)

             {

                 j=binarySearch(j,i,n,k);

                 ans+=i-j+;

             }

             printf("%I64d\n",ans);

         }

     }

     return ;

 }

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <algorithm>

 using namespace std ;

 #define LL __int64

 deque <LL> deq1 , deq2 ;

 //单调队列，deq1最大值，deq2最小值

 LL a[] ;

 int main() {

     int t , n , i , j ;

     LL k , ans ;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     scanf("%d", &t) ;

     while( t-- ) {

         scanf("%d %I64d", &n, &k) ;

         for(i =  ; i < n ; i++)

             scanf("%I64d", &a[i]) ;

         if(k == ) {

             printf("0\n") ;

             continue ;

         }

         while( !deq1.empty() ) deq1.pop_back() ;

         while( !deq2.empty() ) deq2.pop_back() ;

         for(i =  , j =  , ans = ; i < n ; i++) {//i在前，j在后

             while( !deq1.empty() && deq1.back() < a[i] ) deq1.pop_back() ;

             deq1.push_back(a[i]) ;

             while( !deq2.empty() && deq2.back() > a[i] ) deq2.pop_back() ;

             deq2.push_back(a[i]) ;

             while( !deq1.empty() && !deq2.empty() && deq1.front() - deq2.front() >= k ) {

                 ans += (i-j) ;

                 //printf("%d %d,%I64d %I64d\n", i , j, deq1.front() , deq2.front() ) ;

                 if( deq1.front() == a[j] ) deq1.pop_front() ;

                 if( deq2.front() == a[j] ) deq2.pop_front() ;

                 j++ ;

             }

         }

         while( j < n ) {

             ans += (i-j) ;

             j++ ;

         }

         printf("%I64d\n", ans) ;

     }

     return  ;

 }