Description：

有一把刷子宽度为 $M$ 米， $N$ 列的栅栏，每次从栅栏的底部向上刷，对于连续的 $M$ 列栅栏，刷到的高度只能 $M$ 列栅栏的最低高度。求最少有多少个单位面积不能刷到以及最少刷几次。

$1\leqslant n\leqslant10^6$

Solution：

先用单调队列预处理出 $v[i]$ 表示以 $i$ 为右端点刷能刷到的最大高度，在对 $v[i]$ 做单调队列就可以求出每个位置能被覆盖的最高位置 $s[i]$ ，然后第一问的答案就是： $$ \sum_{i=1}^n(h[i]-s[i]) $$

然后第二问贪心，我们肯定希望刷一次能覆盖掉尽量多的 $s[i]$ ，所以用一个 $DP$ 的做法，一直刷到刷子不够长或者上一个 $s[j]$ 和当前 $s[i]$ 不同，转移为 $f[i]=f[i-\min(m,len)]$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

inline int rd()

{

	R int res = 0,f = 1;

	R char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 1000010

int h[MAXN];

int q[MAXN],hd,tl;

int v[MAXN],s[MAXN];

#define INF 0x3f3f3f3f

int f[MAXN];

int main()

{

	freopen("wyt.in","r",stdin);

	freopen("wyt.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(R int i = 1;i <= n;++i)h[i] = rd();

	hd = 1;tl = 0;

	for(int i = 1;i < m;++i)

	{

		while(hd <= tl && h[q[tl]] > h[i])--tl;

		q[++tl] = i;

		v[i] = -INF;

	}

	for(int i = m;i <= n;++i)

	{

		while(hd <= tl && h[q[tl]] > h[i])--tl;

		q[++tl] = i;

		while(hd <= tl && q[hd] < i - m + 1)++hd;

		v[i] = h[q[hd]];

	}

	hd = 1;tl = 0;

	for(int i = n;i > n - m + 1;--i)

	{

		while(hd <= tl && v[q[tl]] < v[i])--tl;

		q[++tl] = i;

		s[i] = v[q[hd]];

	}

	for(int i = n - m + 1;i >= 1;--i)

	{

		while(hd <= tl && v[q[tl]] < v[i])--tl;

		q[++tl] = i;

		while(hd <= tl && q[hd] > i + m - 1)++hd;

		s[i] = v[q[hd]];

	}

	long long ans1 = 0;

	for(int i = 1;i <= n;++i)ans1 += h[i] - s[i];

	cout << ans1 << endl;

	int len = 0;

	for(int i = 1;i <= n;++i)

	{

		if(i != 1 && s[i] == s[i - 1])++len;

		else len = 1;

		f[i] = f[i - min(len,m)] + 1;

	}

	cout << f[n] << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}