提供一种优先队列的做法。

首先，最长序列的长度一定等于数组中有多少不同的数，我们设其为 $m$。

因此，我们选的第一个数，一定是在所有选了它之后还能再选 $m-1$ 个不同数的数里面，选一个最大的数。

记该数的位置为 $a$ ，其在数组中出现的最后一个位置为 $b$ ，设 $suf[i]$ 代表从这个数开始选，能选多少不同的数。

则有 $(a,b)$ 内所有的 $suf[i]$ 都减一，因为对于 $(a,b)$ 内的数来说，位置 $b$ 处数是作为一个新的不同数存在的，但是又不能选，所以减一

code

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

struct node1
{
    int val,index;
    bool operator<(const node1 &b) const
    {
        if(b.val!=val)return b.val<val;
        else return b.index<index;
    }
};

struct node2
{
    int val,index;
    bool operator<(const node2 &b) const
    {
        if(b.val!=val)return b.val>val;
        else return b.index<index;
    }
};

int a[300005];
void solve()
{
    int n;
    cin>>n;

    priority_queue<node1> qmin;
    priority_queue<node2> qmax;

    for(int i=1;i<=n;i++) cin>>a[i];

    map<int,int> rec;
    stack<int> split;
    for(int i=n;i>=1;i--)
    {
        if(!rec[a[i]])
        {
            split.push(i);
            rec[a[i]]=i;
        }
    }

    int it=1;
    int r=split.top();
    split.pop();
    int op=1;
    map<int,int> vis;
    int l=1;
    vector<int> ans;
    int num=rec.size();

    set<int> finish;
    while(num)
    {
        while(it<=r)
        {
            qmax.push({a[it],it});
            qmin.push({a[it],it});
            it++;
        }

        while(!qmax.empty() && (vis[qmax.top().val]||qmax.top().index<l)) qmax.pop();
        while(!qmin.empty() && (vis[qmin.top().val]||qmin.top().index<l)) qmin.pop();

        if(op)
        {
            if(!qmax.empty())
            {
                auto [val,index]=qmax.top();
                l=index+1;
                vis[val]=1;
                ans.push_back(val);
                finish.insert(rec[val]);
            }
        }
        else
        {
            while(!qmin.empty() && vis[qmin.top().val]) qmin.pop();
            if(!qmin.empty())
            {
                auto [val,index]=qmin.top();
                l=index+1;
                vis[val]=1;
                ans.push_back(val);
                finish.insert(rec[val]);
            }
        }


        while(finish.count(r) && !split.empty())
        {
            r=split.top();
            split.pop();
        }

        num--;
        op^=1;

    }
    cout<<ans.size()<<'\n';
    for(auto it: ans )cout<<it<<' ';
    cout<<"\n\n";
}
signed main()
{
    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TT=1;
    cin>>TT;
    while(TT--) solve();
    return 0;
}

JIUZHE

D. Longest Max Min Subsequence

code