BZOJ

分析

正着很难想，考虑反着做。

已知一个非降序列，将其分成尽量少的几段，使得每一段对应一个合法的双端队列。

然后发现一个合法的双端队列，一定满足下标先递减再递增。

然后就可以先sort，再贪心地凑。

对于相同的数，它们的顺序是可以交换的。显然下标递增或递减时最优。

然后就可以按照相同的数去划，每一个区间往后放，尽量的使得这样的单谷区间少。

举一个样例的例子：

$A=[[0],[3,3],[6,6],[9]],B=[[3],[1,6],[2,5],4]]$

先接$[0]$，下标变成$[3]$；然后接$[3,3]$，下标无法再递减，变成$[3,1,6]$；接$[6,6]$，下标无法再递增，变成$[3,1,6,5,2]$；最后接$[9]$，无法再递减，变成$[3,1,6,5,2,4]$。共有两个单谷段，答案为2。

可以每次开始递减时就ans++。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=200000+10;

struct node {
    int val,pos;
    bool operator <(const node& rhs) const {
        return (val<rhs.val)||((val==rhs.val)&&(pos<rhs.pos));
    }
};

node a[MAXN];
int Min[MAXN],Max[MAXN];

int main() {
    int n=read();
    for (re int i=1;i<=n;++i) a[i].val=read(),a[i].pos=i;
    sort(a+1,a+n+1);
    int cnt=0;
    for (re int i=1;i<=n;++i)
        if (a[i].val!=a[i-1].val||i==1)
            Max[cnt]=a[i-1].pos,Min[++cnt]=a[i].pos;
    Max[cnt]=a[n].pos;
    int ans=1,last=Min[1],flag=0; //flag为0则递减，1则递增
    //这里ans=1是考虑第一段，是一个递减区间。
    for (re int i=2;i<=cnt;++i) {
        if (!flag) {
            if (last<Max[i]) flag=1,last=Max[i];
            else last=Min[i];
        }
        else {
            if (last>Min[i]) ++ans,flag=0,last=Min[i];
            else last=Max[i];
        }
    }
    printf("%d\n",ans);
    return 0;
}