2015 多校联合集训 第一场

暑假因为出去参加夏令营和各种事情，没有跟留在学校训练的小伙伴们一起打多校，想想还是挺惭愧的。

从大一进校开始，ACM已经打了快4年了，如果所有事情都弄完了，下半年可能还有机会最后收个尾…（咳咳，话说我退役贴都早写过了…）

试看了几题，发现这么长时间没有写题，思路都跟不上了。唉。

开始尝试补一下多校题吧。

HDU 5289 1002 Assignment

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Tom owns a company and he is the boss. There are n staffs which are numbered from 1 to n in this company, and every staff has a ability. Now, Tom is going to assign a special task to some staffs who were in the same group. In a group, the difference of the ability of any two staff is less than k, and their numbers are continuous. Tom want to know the number of groups like this.

Input

In the first line a number T indicates the number of test cases. Then for each case the first line contain 2 numbers n, k (1<=n<=100000, 0<k<=10^9),indicate the company has n persons, k means the maximum difference between abilities of staff in a group is less than k. The second line contains n integers:a[1],a[2],…,an,indicate the i-th staff’s ability.

Output

For each test，output the number of groups.

Sample Input

2
4 2
3 1 2 4
10 5
0 3 4 5 2 1 6 7 8 9

Sample Output

5
28

Hint

First Sample, the satisfied groups include:[1,1]、[2,2]、[3,3]、[4,4] 、[2,3]

分析

真是落后了，看着题解还花了好长时间才想明白。。。

题目求的是连续的最大最小值之差不超过K的子序列的总个数。

因为要求子序列的连续性，本题可以使用单调队列的思想来解决。可以想象成一个滑动窗口从前面开始不断向后移动，需要维护的是两个指针：窗口的左端和右端。

1. 对于窗口的右端：
   读入新的数据就可以看成是一个窗口右端不断右移的过程，我们需要做的就是对于每一个新加入的点，处理左端指针；
2. 处理左端指针的过程，我们需要用到两个单调队列分别保存当前窗口的最大值和最小值：
   当当前窗口中的最大值与最小值的差值大于等于K的时候，就是左端指针需要右移的时候。

/* ***********************************************
MYID	: Chen Fan
LANG	: G++
PROG	: HDU 5289
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int a[100010],mi[100010],ma[100010];

int main()
{
	int t;
	scanf("%d",&t);

	for (int tt=1;tt<=t;tt++)
	{
		int n,k;
		scanf("%d%d",&n,&k);

		int heada=1,headi=1,taila=0,taili=0;

		int front=1;

		long long ans=0;

		for (int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);

			while (heada<=taila&&a[ma[taila]]<=a[i]) taila--;
			while (headi<=taili&&a[mi[taili]]>=a[i]) taili--;

			taila++;
			ma[taila]=i;
			taili++;
			mi[taili]=i;

			while (a[ma[heada]]-a[mi[headi]]>=k)
			{
				if (front==ma[heada]) heada++;
				if (front==mi[headi]) headi++;

				front++;
			}

			ans+=i-front+1;
		}

		printf("%lld\n",ans);
	}

	return 0;
}