专项练习：单调队列优化

[Wizmann]

https://vjudge.net/contest/236384

[Wizmann]

A题： 滑动窗口统计，可以用multiset来做，也可以用单调队列。

B题:

• 方法1：使用multiset做统计，O(nlogn)，目测会被卡
• 方法2：单调队列存人的ID，O(n)应该是正解

不想做的原因是怕被卡IO，毕竟这个输入数据也太大了点。。。

D题，单调队列求不大于K的区间和最大。难度3星，可以O(n)做。 关键是想明白单调队列里面存什么，怎么存。

代码：https://github.com/Wizmann/ACM-ICPC/blob/78672180dccff185d4ea9d0f8bf5cdf054072b84/HDU%20OJ/3/3415.cc

[Wizmann]

C题，没用单调队列，用了DP+优化trick。差点没把自己写死。大家可以实践一下。

E题，首先有一个结论。就是一个子数组的最大最小值差小于m的时候，不需要弹出子数组中的任何数，因为并不会让最大最小值差变的更大。暴力解法是用multiset可以维护最大最小值，我们求最大最小值差小于等于k的子数组即可。优雅解法是用两个deque维护最大最小值，这个有点trick，但是还属于单调队列的思想。

[Wizmann]

G题，陈题了， 求最小值所在的最大区间。 F题，又是一道DP实现题。原理很简单，就是求一个终点已知，并且路径之和小于K的子数组。这个我们可以使用单调队列来解决，维护一个由大到小排列的单调队列，然后每加入一个新元素，就从队尾弹出超出路径限制的元素，以及从队首弹出小于当前元素的值的元素。由于游行车可以向左右两边走，所以我们要做两遍DP。

[Wizmann]

H题，算是比较简单的DP+区间最大值优化。不过要写四个方向，就比较日狗。