Points on Line(队列应用)

问题描述：
Little Petya likes points a lot. Recently his mom has presented him n points lying on the line OX. Now Petya is wondering in how many ways he can choose three distinct points so that the distance between the two farthest of them doesn’t exceed d.

Note that the order of the points inside the group of three chosen points doesn’t matter.

Input
The first line contains two integers: n and d (1 ≤ n ≤ 10^5; 1 ≤ d ≤ 10^9). The next line contains n integers x1, x2, …, xn, their absolute value doesn’t exceed 10^9 — the x-coordinates of the points that Petya has got.

It is guaranteed that the coordinates of the points in the input strictly increase.

Output
Print a single integer — the number of groups of three points, where the distance between two farthest points doesn’t exceed d.

Examples
Input

4 3
1 2 3 4
Output

4
Input

4 2
-3 -2 -1 0
Output

2

实现代码如下：

#include<iostream>
#include<queue>
using namespace std;

int main()
{
	long n, distance, len = 0, temp;
	long long sum = 0;
	cin >> n >> distance;

	int *loca = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> loca[i];
	}

	queue<int>numque;
	numque.push(loca[0]);
	len++;
	for (int i = 1; i < n; i++)
	{
		temp = loca[i];
		if ( len == 0||temp - numque.front() <= distance)
		{
			numque.push(temp);
			len++;
		}
		else
		{
			numque.pop();
			i--;
			len--;	
			if (len >=2 )
				sum += (len*(len - 1)/2);
		}
	}
	if(len >2)
		sum += (len*(len - 1)*(len - 2) / 6);
	cout << sum << endl;
}