Sherry现在碰到了一个棘手的问题，有Ｎ个整数需要排序。 Sherry手头能用的工具就是若干个双端队列。 她需要依次处理这N个数，对于每个数，Sherry能做以下两件事： 1．新建一个双端队列，并将当前数作为这个队列中的唯一的数； 2．将当前数放入已有的队列的头之前或者尾之后。 对所有的数处理完成之后，Sherry将这些队列排序后就可以得到一个非降的序列。
第一行包含一个整数N，表示整数的个数。接下来的N行每行包含一个整数Di，其中Di表示所需处理的整数。
其中只包含一行，为Sherry最少需要的双端队列数。
6 3 6 0 9 6 3
2
100%的数据中N≤200000。
1.这道题虽然叫做双端队列，但是如果要使用deque(双端队列)来解的话那么只会gg，重要的是理解deque的特性只能在对头或队尾进行增删。 2.观察这道题的数据规模，发现是两万，如果算法是O(n^2)的话那么就直接gg了，如果是O(n logn)，在每一次操作的比较多的话，那么也会超时，所以得用O(n)的算法qwq。 3.如何在只扫描一遍的情况下ac这道题，首先我们要排除掉模拟的方法，因为模拟的话铁定超时，那么怎么办？寻求一个单个双端队列的本质：1.它是一个单调的队列，是升序（非降序）；2.所有队列合起来，会得到一个更大的单调队列。这很像一个排序的思想，而将多个有序队列合并成一个更大的有序队列，这不正是大名鼎鼎的合并排序了吗？ 4.现在问题已经被简化了，我们只需要求出这次的合并排序中，最少会被分成多少个有序的小组就对了。（注意：小组之间有时是可以合并的，例如[1,2,3],可以和[5,4,3]合并为[1,2,3,3,4,5]） 5.如何在常数时间内解决这道题呢？我们可以先得到已经排好序的有序队列，然后再与这个序列进行对比。
最开始的时候数列是 3 6 0 9 6 3 我们最后会得到的序列是 9 6 6 3 3 0 去掉重复的值 9 6 3 0 发现9和6在一起，6和3在一起，3和0在一起 拆分我们现在的序列 [3 6] [0 9] [6 3]; 合并 -> [3 6 9] [0 3 6]
神奇的事情发生了，我们居然得到了样例的答案！
但是这还没完，时间复杂度，还不够，离答案只剩一点点了！
这样虽然大大简化了难度和时间复杂度（相对于模拟），但是仍不足以支持我们ac，因为得到临近顺序之后再一个个比较的工作量是巨大的，有没有什么办法可以让这个队列的合并从一开始就决定了？亦或是根本就不知道它怎么合并就可以得到答案？蒟蒻的我想不出后者，所以只能绞尽脑汁在前者上面做功夫。 ---------- 由于排序的是数字的值，我们可以反过来想，我们要干的事就是要在这个值里面找到可以相呼应的区间，那么在排序的时候就得存下它的下标（序号）num，在重新扫描已经排好的序列的时候，就可以直接找扫描序列中下标的‘拐点’，也就是单调性发生改变的点。因为数组下标（num）代表的是这个数在序列中的位置，并且我们扫描的是已经排好的序列，那么在同一个单调的序列中，下标单调性改变的话就必然排不起来那么就需要另一个队列。 题目说道这里已经很清楚了，下面直接上代码~~！
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int maxn=2e5+10; const int inf = 2e9; int ans = 1; int f = 1,noww=inf; struct node { int tail, p; } s[maxn]; bool cmp(node x, node y) { if (x.tail == y.tail) return x.p < y.p; return x.tail < y.tail; } int main() { int n; cin>>n; for (int i = 1; i <= n; i++) { scanf("%d", &s[i].tail); s[i].p = i; } sort(s + 1, s + n + 1, cmp); for (int i = 1; i <= n; ) { int j = i; while (s[j + 1].tail == s[j].tail && j < n) j++; if (f == 1) { if(s[j].p<noww) noww=s[i].p; else { f=0; noww=s[j].p; } } else { if(s[i].p>noww) noww=s[j].p; else { f=1; ans++; noww=s[i].p; } } i = j+1; } cout<<ans; return 0; }