BZOJ2457 双端队列

题意

需要用双端队列实现 $N$ 个数的排序。依次处理每一个数，每次只能将数放在队首或队尾，或新建一个队列。求需要的最少双端队列数。

$N\le 200000$ 。

题解

将原数列排序，可以得到 新数列对应原序列下标 的序列。如：

可以发现只有下标序列的一段满足先递减再递增（单谷），才能用一个双端队列实现。因为最小的数先处理，然后才能处理左右序号比它大的数。

不过原序列中相同的数对应的下标序列中的数可以交换位置，使得答案更优。如将 $[2,5]$ 交换位置可以只用 $2$ 个队列，若不交换则需要 $3$ 个。考虑贪心使得当前尽量形成单谷。

排序时用下标作为第二关键字，对于排序好的序列，记录相同的值的起点 $st$ 和终点 $ed$ ，显然两者分别为下标最小和最大值。

然后遍历每一个值，记录之间序列中最后一个下标 $last$ 和 序列状态 $flag$ （$0$ 表示递减，反之递增），作如下分类讨论：

1. 序列递减且 $ed[i]>last$ ，没法继续单调递减，只有单调递增，更新 $last=ed[i]$
2. 序列递增且 $st[i]<last$ ，没法继续递增，改为单调递减，同时 $ans++$ ，更新 $last=ed[i]$
3. 否则继续递减或递增

#include<bits/stdc++.h>

using namespace std;

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

struct node {
    int s,id;
} s[200005];
int n,cnt,st[200005],ed[200005];

inline bool cmp(const node &x,const node &y) { return x.s==y.s ? x.id<y.id : x.s<y.s; }

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i].s=read(),s[i].id=i;
    sort(s+1,s+n+1,cmp);
    st[++cnt]=s[1].id;
    for (int i=2;i<=n;i++)
    {
        if (s[i].s==s[i-1].s) continue;
        ed[cnt]=s[i-1].id;
        st[++cnt]=s[i].id;
    }
    ed[cnt]=s[n].id;
    int last=st[1],ans=1; bool now=0;
    for (int i=2;i<=cnt;i++)
    {
        if (!now && ed[i]>last) now=1;
        else if (now && st[i]<last) ans++,now=0;
        last=now ? ed[i] : st[i];
    }
    return !printf("%d",ans);
}