Pilots POI2010

题意

给定和一个长度为的序列，求最长的最大值最小值相差不超过的区间长度。

输入

第一行两个有空格隔开的整数，，$ t $代表设定的最大值，$ n $ 代表序列的长度。第二行为n个由空格隔开的整数 $（）$ ，表示序列。

输出

一个整数代表最大的符合条件的区间长度。

样例

1 2	3 9 5 1 3 5 8 6 6 9 10

样例解释：5, 8, 6, 6 和8, 6, 6, 9都是满足条件长度为4的序列

解法

定义：如果一个区间的最大最小值的差值不超过 t，则把这个区间称为 t-稳定的。

暴力，枚举区间首尾，判断该区间是否为 t-稳定的，维护答案，总复杂度，不太行。

观察一下，我们发现，如果一个区间不是t-稳定的，那么它所有的母区间也肯定不是t-稳定的。所以，枚举起点，对于每个起点，我们只需要循环到区间正好破坏t-稳定条件就可以停了，然后更新答案，继续判断下一个起点。总复杂度是，还是不太行。

整点数据结构。一个优化是对于每个起点，我们没必要考虑比当前答案小的区间，所以如果破坏了稳定性，我们可以从起点缩小区间，直到区间重新稳定，然后再将终点向后移动，维护答案。这个思路可以通过用一颗平衡树支持插入、删除、查询最值的操作来完成。每个操作的复杂度为，每种操作会被执行次，所以总复杂度是，听上去还行。当然，各种 RMQ 也是可以的，用 O(n)-O(1) RMQ 甚至可以把总复杂度直接降到，但是太数据结构了，不够优雅（低情商：学不会，高情商：不够优雅

观察一下，我们发现，破坏t-稳定条件的元素肯定是当前区间的最小值或者最大值，所以我们不用维护所有的元素，而是只需要维护可能成为最值的元素。本质上，我们需要实现支持以下操作的线性数据结构：在末尾添加一个数、在开始删除一个数、查询序列的最值。所有操作要求均摊复杂度。在题解里，这个方法叫做 Linear implementation specific to this problem ，翻译过成中文就是单调队列（？

单调队列是这样一个东西：考虑队尾插入、队首弹出和维护序列最大值，如果我们加进来的东西比队尾大，那么当前序列里所有比加进来的东西小的值都不可能成为序列最大值了。为什么呢，因为所有比加进来的东西小的值都比加进来的东西小，所以我们把这些元素都弹出去，然后把新元素加进去。如果我们加进来的东西比队尾小，那么等当前的队尾弹出去了之后这个新加进来的东西还是有希望成为最大值的，所以我们把它留下。这样就完成了在末尾添加一个数的操作，这个东西为什么是均摊的呢，感性理解一下就是因为每个数只会被弹出去一次。在开头删除一个数就是在开头删除一个数，注意到有可能你想删除的数早就被弹出去了，所以要先判断一下。查询最值就是查询队首的数，因为所有加进来的数都肯定比前一个数小，所以它是单调减的。所有操作都可以用一个 std::deque 维护，板子差不多长这样：

template <typename T, bool Max = true>
class MonotonePriorityQueue {
private:
	std::deque<T> data;
public:
	void push(T n) {
		while (!data.empty() && Max ^ (data.back() < n))
			data.pop_back();
		data.push_back(n);
	}
	int query() {
		return data.front();
	}
	void pop(T n) {
		if (!data.empty() && data.front() == n)
			data.pop_front();
	}
};

最后就可以实现我们的算法了。使用两个单调队列 up 和 down 维护当前的 t-稳定区间中的最大值和最小值和它们的下标。枚举区间的结尾，如果它和当前队列中最大值的差值超过 t，弹出 up 的队首，记录下标。对 down 队列执行同样操作。那么区间的开头就是。然后对两个队列执行单调队列的 push 操作。然后更新答案，就做完了。总的时间复杂度为。

代码

#include <iostream>
#include <algorithm>
#include <deque>

const int maxn = 3e6+7;

int t, n, a[maxn];
std::deque<std::pair<int, int>> up, down;

int main(int argc, char *argv[]) {  
	std::ios::sync_with_stdio(false);
	std::cin.tie(0); 
	std::cin >> t >> n;
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
	}
	int last_up = 0, last_down = 0;
	int record = 1;
	for (int j = 1; j <= n; j++) {
		auto x = std::make_pair(j, a[j]);
		while (!up.empty() && up.front().second - t > a[j]) {
			last_up = up.front().first;
			up.pop_front();
		}
		while (!down.empty() && down.front().second + t < a[j]) {
			last_down = down.front().first;
			down.pop_front();
		}
		int i = std::max(last_up+1, last_down+1);
		while (!up.empty() && up.back().second < a[j]) {
			up.pop_back();
		}
		up.push_back(x);
		while (!down.empty() && down.back().second > a[j]) {
			down.pop_back();
		}
		down.push_back(x);
		if (j - i + 1 > record) {
			record = j - i + 1;
		}
	}
	std::cout << record << '\n';
}

吐槽

科技在进步，当时看上去大家还不怎么会单调队列，这个题解作者搞得十分隆重... 还挺好的

题解还是提到了 RMQ 的做法的，题解："this algorithm is a bit tricky to implement" ，高情商，我感动了

语言漩涡

POI2010 Pilots 单调队列

Pilots POI2010

题意

输入

输出

样例

解法

代码

吐槽