Codeforces Round 967 (Div. 2) D. Longest Max Min Subsequence ("单调"栈)

chenmingeng · 2024-08-21 21:32:51 · 题解

——提供一种线性方法

题意

求正整数序列 a 的每个元素恰好出现一次的子序列中，将奇数位置上的项乘以 -1 后字典序最小的序列。数据范围：1 \leqslant a_{i} \leqslant n \leqslant 3\times 10^{5}。

思路

问题等价于最大化奇数位，最小化偶数位。

引例

先考虑这样的问题：求每个元素恰好出现一次的子序列中字典序最小的序列。

维护一个栈。

从前向后遍历，如果新加入的元素比栈尾元素小，就将其弹出，以保证字典序最小。

还有一个问题是可能弹出后这个元素就没有出现过了，故加上两个特判：

• 一是如果已经在栈中，就不做处理，用 vis 数组判断；
• 二是如果栈尾元素在序列中最后一次出现，就不弹出，用 lst 数组判断。

void eachT() {
    int n = read();

    vector<int> a(n), lst(n);
    for (int i = 0; i < n; ++i) {
        a[i] = read() - 1;
        lst[a[i]] = i;
    }

    vector<int> vis(n);
    deque<int> stk;
    for (int i = 0; i < n; ++i) {
        if (vis[a[i]]) continue;
        while (!stk.empty() && a[stk.back()] > a[i] && lst[a[stk.back()]] > i) {
            vis[a[stk.back()]] = 0;
            stk.pop_back();
        }
        stk.push_back(i);
        vis[a[i]] = 1;
    }

    printf("%d\n", stk.size());
    for (int i = 0; i < stk.size(); ++i) {
        printf("%d ", a[stk[i]] + 1);
    }
    printf("\n");
}

回到原问题

与上面不同的是，需要依据栈的大小改变大于小于号，维护一个波浪形的栈。

测样例后发现 4 1 4 5 4 5 10 1 5 1，错解为 4 1 10 5，正解为 5 4 10 1，栈中有 4 1，5 应该将这两个数都弹出后再入栈，但是按上面的写法 1<5，不用弹出，补上直接弹出栈尾的两个元素的情形就好了。

时空复杂度 \Theta(n)。

代码

因为需要访问倒数第二个元素，没有用 std::stack。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
inline ll read() {
    ll S = 0, C = 0; char Y = getchar();
    while (Y > 57 || Y < 48) C |= Y == 45, Y = getchar();
    while (Y <= 57 && Y >= 48) S = (S << 3) + (S << 1) + Y - 48, Y = getchar();
    return C ? -S : S;
}

void beforeT() {}
void eachT() {
    int n = read();

    vector<int> a(n), lst(n);
    for (int i = 0; i < n; ++i) {
        a[i] = read() - 1;
        lst[a[i]] = i;
    }

    int top = -1;
    vector<int> stk(n), vis(n);
    for (int i = 0; i < n; ++i) {
        if (vis[a[i]]) continue;
        while (top >= 0 && (top & 1 ? a[stk[top]] > a[i] : a[stk[top]] < a[i]) && lst[a[stk[top]]] > i) {
            vis[a[stk[top--]]] = 0;
        }
        while (top >= 1 && (top & 1 ? a[stk[top - 1]] < a[i] : a[stk[top - 1]] > a[i]) && lst[a[stk[top - 1]]] > i && lst[a[stk[top]]] > i) {
            vis[a[stk[top--]]] = 0;
            vis[a[stk[top--]]] = 0;
        }
        vis[a[stk[++top] = i]] = 1;
    }

    printf("%d\n", top + 1);
    for (int i = 0; i <= top; ++i) {
        printf("%d ", a[stk[i]] + 1);
    }
    printf("\n");
}

int main() {
    beforeT();
    for (int T = read(); T--; eachT());
    return 0;
}