Assignment(枚举 二分 rmq) 1002

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int n,k;
 8 int a[100005];
 9 int ma[100005][30],mi[100005][30];
10 
11 void inrmq()
12 {
13     int i,j;
14     for(j=1;(1<<j)<=n;j++)
15     {
16         for(i=1;i+(1<<j)-1<=n;i++)
17         {
18             ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]);
19             mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
20         }
21     }
22     return ;
23 }
24 
25 int rmqjudge(int l,int r)
26 {
27     int kk=(int)(log(r-l+1.0)/log(2.0));
28     return (max(ma[l][kk],ma[r-(1<<kk)+1][kk])-min(mi[l][kk],mi[r-(1<<kk)+1][kk]))<k;
29 }
30 
31 int main()
32 {
33     int T;
34     int i,j;
35     scanf("%d",&T);
36     while(T--)
37     {
38         scanf("%d %d",&n,&k);
39         for(i=1;i<=n;i++)
40         {
41             scanf("%d",&a[i]);
42             ma[i][0]=a[i];
43             mi[i][0]=a[i];
44         }
45         inrmq();
46         long long ans=0;
47         int l,r,p,mid;
48         for(i=1;i<=n;i++)
49         {
50             l=i;
51             r=n;
52             while(l<=r)
53             {
54                 mid=(l+r)>>1;
55                 if(rmqjudge(i,mid))
56                 {
57                     p=mid;
58                     l=mid+1;
59                 }
60                 else
61                     r=mid-1;
62             }
63             ans=ans+p-i+1;
64         }
65         printf("%I64d\n",ans);
66     }
67     return 0;
68 }