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

· · 题解

——提供一种线性方法

题意

求正整数序列 A 的每个元素恰好出现一次的子序列中，将奇数位置上的项乘以 -1 后字典序最小的序列。

数据范围：1 \leqslant A_{i} \leqslant N \leqslant 3\times 10^{5}。

思路

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

引例

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

维护一个栈。

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

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

  1. 如果已经在栈中，就不做处理，用 vis 数组判断；
  2. 如果栈尾元素在序列中最后一次出现，就不弹出，用 lst 数组判断。
void solve() {
    int N;
    std::cin >> N;

    std::vector<int> A(N), lst(N);
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
        A[i]--;
        lst[A[i]] = i;
    }

    std::vector<int> vis(N);
    std::stack<int> stk;
    for (int i = 0; i < N; i++) {
        if (vis[A[i]]) continue;
        while (!stk.empty() && A[stk.top()] > A[i] && lst[A[stk.top()]] > i) {
            vis[A[stk.top()]] = 0;
            stk.pop();
        }
        stk.push(i);
        vis[A[i]] = 1;
    }

    std::cout << stk.size() << "\n";
    for (int i = 0; i < stk.size(); i++) {
        std::cout << A[stk[i]] + 1 << " ";
    }
    std::cout << "\n";
}

回到原问题

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

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

时空复杂度 \mathcal{O}(n)。

代码

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

#include <bits/stdc++.h>

void solve() {
    int N;
    std::cin >> N;

    std::vector<int> A(N), lst(N);
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
        A[i]--;
        lst[A[i]] = i;
    }

    int top = -1;
    std::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;
    }

    std::cout << top + 1 << "\n";
    for (int i = 0; i <= top; i++) {
        std::cout << A[stk[i]] + 1 << " ";
    }
    std::cout << "\n";
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    std::cin >> T;
    while (T--) solve();
    return 0;
}