分数: 466 分
问题陈述
高桥在气象观测站工作,正在记录超过 N 特定区域的天数。当日最高气温 i (1 \leq i \leq N) 是 A_i ℃.
Takahashi 希望选择连续的天数间隔并检查温度波动范围。从一天开始的一个时间间隔 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 (仅包含一天的区间),波动范围为 0.
给定一个正整数 N,一个非负整数 K,以及一系列最高温度 N 天 A_1, A_2, \dots, A_N,找出波动范围恰好为的区间数 K。即求整数对的个数 (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) = K
约束
- 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
第一行包含一个正整数 N 表示天数,非负整数 K 代表指定的波动范围,以空格分隔。第二行包含整数 A_1, A_2, \dots, A_N 代表每天的最高气温,以空格分隔。
输出
输出对数 (l, r) 其波动范围恰好是 K,在一行上。
示例输入 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