A145357.星尘观测窗
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
Sherry 正在记录一条星尘轨道上的能量变化。轨道上有 n 个观测点,第 i 个观测点的能量值为 ai。
她想选择一段连续的观测区间 [l,r]。如果这段区间内最大能量值和最小能量值的差不超过 D,那么这段区间就被称为“稳定观测窗”。
请你计算一共有多少个稳定观测窗。
这里的稳定观测窗指的是一个连续区间。只要两个区间的左端点或右端点不同,就认为它们是不同的稳定观测窗。
也就是说,即使一个稳定观测窗可以继续向左或向右延长,并且延长后仍然稳定,原来的区间和延长后的区间也会分别计算。
需要统计满足下面条件的连续区间数量:
max(al,al+1,⋯,ar)−min(al,al+1,⋯,ar)≤D
输入格式
第一行输入两个整数 n,D,分别表示观测点数量和稳定差值上限。
第二行输入 n 个整数 a1,a2,⋯,an,表示每个观测点的能量值。
输出格式
输出一个整数,表示稳定观测窗的数量。
输入输出样例
输入#1
6 3 1 3 2 6 4 5
输出#1
12
输入#2
5 0 2 2 1 1 1
输出#2
9
说明/提示
数据范围
1≤n≤2×105
0≤D≤109
1≤ai≤109
答案可能较大,请使用 long long。
输入解题思路,AI测评打分。不知道怎么写?