Assignment

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

Total Submission(s): 148    Accepted Submission(s): 71

Problem Description

Tom owns a company and he is the boss. There are n staffs which are numbered from 1 to n in this company, and every staff has a ability. Now, Tom is going to assign a special task to some staffs who were in the same group. In a group, the difference of the ability of any two staff is less than k, and their numbers are continuous. Tom want to know the number of groups like this.

 

 

Input

In the first line a number T indicates the number of test cases. Then for each case the first line contain 2 numbers n, k (1<=n<=100000, 0<k<=10^9),indicate the company has n persons, k means the maximum difference between abilities of staff in a group is less than k. The second line contains n integers:a[1],a[2],…,a[n](0<=a[i]<=10^9),indicate the i-th staff’s ability.

 

 

Output

For each test，output the number of groups.

 

 

Sample Input

2 4 2 3 1 2 4 10 5 0 3 4 5 2 1 6 7 8 9

 

 

Sample Output

5 28

Hint

First Sample, the satisfied groups include:[1,1]、[2,2]、[3,3]、[4,4] 、[2,3]

给n个数的序列，找出其中有多少[i , j] 满足最大值和最小值的差小于k枚举左端，if(last>0&&abs(num[i-1]-num[last])
     
      <=last-1必定有  num[x] - num[last] >= k.    所以判断第i个数时先判断i-1，num[i-1]-num[last])
      
       <=last-1不满足条件，则跳过过这次i判断. （感觉这不是什么正常套路）官方解：1. 枚举左端，二分右端，ST求最值2. 用单调队列维护最值如果没这个判断则超时，数据真大 - - ！！
       #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;long long num[101000];long long s(long long i){ return (1+i)*i/2;}int main(){ int t, n, k, minx, maxx, last; long long int re; //freopen("1002.txt","r",stdin); scanf("%d", &t); while(t--) { re = 0; scanf("%d%d", &n, &k); for(int i=1; i<=n; i++) { scanf("%I64d", num+i); } last = -1; for(int i=1; i<=n; i++) { if(last>0&&abs(num[i-1]-num[last])
            
             =k || abs(num[j]-maxx)>=k) { break; } else { if(num[j]
             
              maxx) maxx = num[j]; } } if(last<0) { re += s(j-i); last = j; } else if(j>last) { re += (s(j-i) - s(last-i)); last = j; } } cout<
              
               <
               
                #include 
                
                 using namespace std;int p[200005];int dp1[200005][30],dp2[200005][30];void RMQ_init(int n){ for(int i=1; i<=n; i++) { dp1[i][0]=p[i]; dp2[i][0]=p[i]; } for(int j=1; (1<
                 
                  <=n; j++) { for(int i=1; i+(1<
                  
                   <=n; i++) { dp1[i][j]=max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]); dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]); } }}int rmq(int x,int y){ int k=0; while((1<<(k+1))<=y-x+1)k++; return max(dp1[x][k],dp1[y-(1<
                   
                    <
                    
                     = k && temp