题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2457
Description
Sherry现在碰到了一个棘手的问题，有Ｎ个整数需要排序。
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。
题解：
假设原序列 $D$ 排序后的序列为 $E$。换句话说，我们就是要将 $E$ 分成若干段，每一段对应原来的一个双端队列。
现在考虑如何切割 $E$，假设现在我们分割出了其中某一段 $S_1 sim S_n$，那么其中必然有一个数 $S_k(1 le k le n)$ 是第一个进入队列的。
那么 $S_1 sim S_{k-1}$ 这些数在 $D$ 中的出现顺序必须是降序的。换句话说，在 $S_1 sim S_{k-1}$ 中，$S_1$ 必须是最后一个在 $D$ 中出现的。这是很显然的，它作为最小的，显然必须最后一个push进双端队列的队首。
同样的道理，$S_{k+1} sim S_n$ 这些数在 $D$ 中的出现顺序必须是升序的。$S_n$ 它作为最大的一个，必须最后一个push进双端队列的队尾。
也就是说，在 $E$ 中尽可能少地分割出若干段，每段都满足其内部的数在 $D$ 中的出现顺序是先降后升的。这个可以用贪心策略求最少段数。
另外要考虑的一个问题是，同一个数可能在 $D$ 中不同位置出现，那么我们应当让他们在 $E$ 中有一个合适的顺序，使得分割产生的段数尽量少。这个可以做个分类讨论。
AC代码：
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; const int maxn=2e5+10; int n; pii a[maxn]; int tot; pii bnd[maxn]; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].first; a[i].second=i; } sort(a+1,a+n+1); tot=0; for(int i=1;i<=n;i++) { //printf("val=%d pos=%d ",a[i].first,a[i].second); if(i==1 || a[i].first!=a[i-1].first) { bnd[tot].second=a[i-1].second; bnd[++tot].first=a[i].second; } } bnd[tot].second=a[n].second; //for(int i=1;i<=tot;i++) printf("[%d,%d] ",bnd[i].first,bnd[i].second); int ans=0, pre=maxn, up=1; for(int i=1;i<=tot;i++) { if(up) { if(pre<bnd[i].first) pre=bnd[i].second; else pre=bnd[i].first, up=0, ans++; } else { if(pre>bnd[i].second) pre=bnd[i].first; else pre=bnd[i].second, up=1; } } cout<<ans<<endl; }