Start Time：2017-07-29 14:00:00 End Time：2017-07-29 16:30:00 Refresh Time：2017-07-29 16:42:55 Private

B -- Buildings

Time Limit：2s Memory Limit：128MByte

Submissions：590Solved：151

DESCRIPTION

There are $\mathrm{nn\; buildings\; lined\; up,\; and\; the\; height\; of\; the\; ii-th\; house\; is\; hihi.}$

An inteval $[l,r][l,r](l\le r)(l\le r)\; is\; harmonious\; if\; and\; only\; if\; max(hl,\dots ,hr)-min(hl,\dots ,hr)\le kmax(hl,\dots ,hr)-min(hl,\dots ,hr)\le k.$

Now you need to calculate the number of harmonious intevals.

INPUT

The first line contains two integers

$\mathrm{n(1\le n\le 2\times 105),k(0\le k\le 109)n(1\le n\le 2\times 105),k(0\le k\le 109).\; The\; second\; line\; contains\; nn\; integers\; hi(1\le hi\le 109)hi(1\le hi\le 109).}$

OUTPUT

Print a line of one number which means the answer.

SAMPLE INPUT

3 1 1 2 3

SAMPLE OUTPUT

5

HINT

Harmonious intervals are:

$[1,1],[2,2],[3,3],[1,2],[2,3][1,1],[2,2],[3,3],[1,2],[2,3].$

$【题意】给你一个序列，然后问你有多少个区间的最大值-最小值<=k。$

$【分析】我们可以用RMQ来logn查询区间最大、最小值，然后枚举每一位最为区间右端点，向左二分左端点，将区间长度加到ans即可。$

#include 
        
         #define inf 0x3f3f3f3f#define met(a,b) memset(a,b,sizeof a)#define pb push_back#define mp make_pair#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;const int N = 2e5+50;const int mod = 1e9+7;const double pi= acos(-1.0);typedef pair
         
          pii;int n,k;int a[N];int mn[N][20],mx[N][20],mm[N];void init() {    for(int j=1; j<=mm[n]; ++j) {        for(int i=1; i+(1<
          
           <=n; ++i) {            mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);        }    }}int getmx(int l,int r) {    int k = mm[r-l+1];    return max(mx[l][k],mx[r-(1<
           
            k)l=mid+1;            else r=mid-1,res=mid;        }        ans+=i-res+1;    }    printf("%lld\n",ans);    return 0;}