【题解】双端队列 思维题（也许思维难度也很低）BZOJ – 2457

题目链接

我们不妨考虑倒着做这题

首先我们把屏幕反过来然后把自己吊在天花板上倒着做就行了

最后把所有的双端队列连起来是一个排好序的序列，就是说一个双端队列里的元素一定是连续的，因此我们把所有元素按照大小为第一关键字，出现时间为第二关键字排序

然后就按照排好序的顺序一个一个处理元素，划分成一个一个双端队列。

一个双端队列是合法的应当满足它里面的元素的出现时间应当满足先下降后上升。

于是就让尽可能多的元素待在同一个队列里了。

如果一个一个元素处理会比较头疼，因此把值相同的元素一起处理，它们一定是可以在同一个双端队列里的。

代码：

#include <bits/stdc++.h>

#define NS (200005)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, ans = 1, mn[NS], mx[NS], cnt;

PII p[NS];

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 1; i <= n; i += 1) IN(p[i].FIR), p[i].SEC = i;
    sort(p + 1, p + 1 + n), p[0].FIR = p[n +1].FIR = INT_MAX;
    for (int i = 1; i <= n; i += 1)
    {
        if (p[i].FIR != p[i - 1].FIR) mn[++cnt] = p[i].SEC;
        if (p[i].FIR != p[i + 1].FIR) mx[cnt] = p[i].SEC;
    }
    bool flag = 1; int cur = INT_MAX;
    for (int i = 1; i <= cnt; i += 1)
    {
        if (flag)
        {
            if (mx[i] < cur) cur = mn[i];
            else cur = mx[i], flag = 0;
        }
        else if (mn[i] > cur) cur = mx[i];
        else ans++, flag = 1, cur = mn[i];
    }
    printf("%d\n", ans);
    return 0;
}