Bzoj2457 双端队列

某一天在晚自习的时候无聊做的思维题。

结果真就做出来了。

Description：

Sherry现在碰到了一个棘手的问题，有N个整数需要排序。
Sherry手头能用的工具就是若干个双端队列。
她需要依次处理这N个数，对于每个数，Sherry能做以下两件事：
1．新建一个双端队列，并将当前数作为这个队列中的唯一的数；
2．将当前数放入已有的队列的头之前或者尾之后。
对所有的数处理完成之后，Sherry将这些队列排序后就可以得到一个非降的序列。

Input
第一行包含一个整数N，表示整数的个数。接下来的N行每行包含一个整数Di，其中Di表示所需处理的整数。
Output
其中只包含一行，为Sherry最少需要的双端队列数。
Sample Input
6 
3 6 0 9 6 3
Sample Output
2
Hint
100%的数据中N≤200000。
Source
Bejing Day1

solution

考虑这道题从何入手，正常想法都是正着取按照要求模拟一下。

但是这道题有些恶心，如果一个双端队列中存在一个相邻的二元组 \((u,v)\)。

且在原序列当中 \((u,v)\) 不相邻。那么就有可能出现一个元素 \(o\)。

满足 \(pos[o] \in (pos[u],pos[v])\) 且 \(o \in (u,v)\)。

（\(pos\) 表示元素在原序列的位置）

那么很明显就是无解了。

因为我们要 按顺序 对原序列进行操作。

最要命的是，这道题很容易出现这种情况，随便构造一个数据就行了。

做数学题的时候有个思想叫 “正难则反” 。

所以我们不妨考虑直接把这个序列变成不下降的，然后再倒推回去（显然这个不下降的序列是唯一的（有相同元素也无妨））。

那么问题可以转化为：

把一个不下降的序列划分成连续的 \(k\) 的子段，使得每一个子段都是可以由原序列经过合法操作得来的。
并求 \(k\) 的最小值。

因为题目的要求是按顺序，所以我们离散化一下，排序的时候记录一下这个元素在原序列的位置 \(pos\) 。

现在考虑一下，怎么样的一个（离散后序列中的）子段才是合法的？

不难得出：对于一个子段，它想要合法，那么它不可能有形如 \(pos={1,7,2}\)
这样子的排列。

因为你不可能把 \(a[1],a[2]\) 插入之后再在它们之间插入一个 \(a[7]\) 啊（\(a[1],a[2]\) 又不能出队）。

说白了就是 \(pos\) 要有单调性，但我们这里是双端队列，两边都能入队（扩展）。

那么分析一下，就有一个性质：

对于一个子段里的 \(pos\) 最小（大）的数，一定满足它两边分别单调。

或者整段单调，甚至可以是就只有他一个元素。

也就是这样子的：

现在随便来一组数据模拟一下：

n=8,a={3,9,4,8,8,9,7,2};

离散之后：

a={2,3,4,7,8,8,9,9}
pos={8,1,3,7,4,5,2,6}

很明显其中一种最优划分是

a : |2 3 4 7|,|8 8 9|,|9|。

pos:|8 1 3 7|,|4 5 2|,|6|。

画一个图：

拆出来就是这样的三段函数：

满足性质。

（实际上就是一个单谷性质）

那么我们离散之后统计一下 \(pos\) 的单调性然后随便贪一贪，分一下就可以了。