/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 466 点
問題文
高橋君は気象観測所で働いており、ある地域の N 日間の日ごとの最高気温を記録しています。i 日目（ 1 \leq i \leq N ）の最高気温は A_i ℃です。
高橋君は、連続する日の区間を選んで気温の変動幅を調べたいと考えています。l 日目から r 日目までの区間（ 1 \leq l \leq r \leq N ）に対して、その区間の「変動幅」を
\max(A_l, A_{l+1}, \dots, A_r) - \min(A_l, A_{l+1}, \dots, A_r)
と定義します。特に、l = r のとき（1日だけからなる区間）の変動幅は 0 です。
正整数 N と非負整数 K、および N 日間の最高気温の列 A_1, A_2, \dots, A_N が与えられたとき、変動幅がちょうど K となる区間の個数、すなわち
\max(A_l, A_{l+1}, \dots, A_r) - \min(A_l, A_{l+1}, \dots, A_r) = K
を満たす整数の組 (l, r)（ 1 \leq l \leq r \leq N ）の個数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数である
入力
N K A_1 A_2 \dots A_N
1 行目には、日数を表す正整数 N と、変動幅として指定された非負整数 K が、スペース区切りで与えられる。2 行目には、各日の最高気温を表す整数 A_1, A_2, \dots, A_N が、スペース区切りで与えられる。
出力
変動幅がちょうど K となる組 (l, r) の個数を 1 行で出力せよ。
入力例 1
5 3 1 4 2 5 3
出力例 1
6
入力例 2
7 0 3 3 3 5 5 3 3
出力例 2
12
入力例 3
10 5 2 -1 3 7 4 0 6 1 5 -2
出力例 3
2
Score : 466 pts
Problem Statement
Takahashi works at a weather observatory and is recording the daily maximum temperatures over N days for a certain region. The maximum temperature on day i (1 \leq i \leq N) is A_i ℃.
Takahashi wants to select a contiguous interval of days and examine the temperature fluctuation range. For an interval from day l to day r (1 \leq l \leq r \leq N), the "fluctuation range" of that interval is defined as:
\max(A_l, A_{l+1}, \dots, A_r) - \min(A_l, A_{l+1}, \dots, A_r)
In particular, when l = r (an interval consisting of only one day), the fluctuation range is 0.
Given a positive integer N, a non-negative integer K, and a sequence of maximum temperatures over N days A_1, A_2, \dots, A_N, find the number of intervals whose fluctuation range is exactly K. That is, find the number of integer pairs (l, r) (1 \leq l \leq r \leq N) satisfying:
\max(A_l, A_{l+1}, \dots, A_r) - \min(A_l, A_{l+1}, \dots, A_r) = K
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- -10^9 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \dots A_N
The first line contains a positive integer N representing the number of days and a non-negative integer K representing the specified fluctuation range, separated by a space. The second line contains integers A_1, A_2, \dots, A_N representing the maximum temperature on each day, separated by spaces.
Output
Output the number of pairs (l, r) whose fluctuation range is exactly K, on a single line.
Sample Input 1
5 3 1 4 2 5 3
Sample Output 1
6
Sample Input 2
7 0 3 3 3 5 5 3 3
Sample Output 2
12
Sample Input 3
10 5 2 -1 3 7 4 0 6 1 5 -2
Sample Output 3
2