CF2001D Longest Max Min Subsequence

Problem - 2001D - Codeforces

Solution

所求序列长度为 $a$ 中的元素种类数。小根堆 $L$ 维护每种元素最后一次出现的位置。

第一步，开大根堆 $D$ 和小根堆 $U$，把位置 $1\sim L_{top}$ 的元素同时放进 $D$ 和 $U$ 中。由于答案序列的第一位是负数，所以要取 $D$ 的堆顶作为答案序列的第一位。然后标记该数字已使用。后续使用 $U$、$D$ 和 $L$ 时，将与该数字相关或出现位置在它之前的成员从堆中弹出。

后续同理，可逐位构造出答案序列。

时间复杂度 $O(n\log n)$。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 10;

int T, n, a[N], loc[N], used[N], tot, ans[N], cnt, tag;
struct Node {
    int x, y;
    friend bool operator > (const Node &a, const Node &b) {
        if (a.x == b.x)
            return a.y < b.y;
        return a.x > b.x;
    }
    friend bool operator < (const Node &a, const Node &b) {
        if (a.x == b.x)
            return a.y > b.y;
        return a.x < b.x;
    }
};
priority_queue<Node> down;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > lst, up;

void solve()
{
    scanf("%d", &n);
    cnt = tot = tag = 0;
    while (down.size()) down.pop();
    while (up.size()) up.pop();
    while (lst.size()) lst.pop();
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        loc[a[i]] = i;
        used[i] = 0;
    }
    for (int i = 1; i <= n; i++)
        if (loc[a[i]] == i)
            lst.push({i, a[i]}), tot++;
    int p = 0;
    while (tot--) {
        while (used[lst.top().second])
            lst.pop();
        while (p < lst.top().first) {
            p++;
            up.push({a[p], p});
            down.push({a[p], p});
        }
        ++cnt;
        if (cnt & 1) {
            while (used[down.top().x] || down.top().y <= tag)
                down.pop();
            ans[cnt] = down.top().x;
            tag = down.top().y;
        } else {
            while (used[up.top().first] || up.top().second <= tag)
                up.pop();
            ans[cnt] = up.top().first;
            tag = up.top().second;
        }
        used[ans[cnt]] = 1;
    }
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; i++)
        printf("%d ", ans[i]);
    putchar('\n');
}

int main()
{
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}