The Best Lineup (USACO Silver 2025 February)

假设我们可以从 $a$ 中以任意顺序取数字，那么这时字典序最大的就是数字从大到小排序的串。首先我们观察到，在有题目中间的限制条件的情况下，我们肯定是要保证取到最长的从大到小排序的前缀。所以问题变成怎么找到最大的前缀，看起来可以贪心地做。就是把排序做出来后，一个个数字看是否可以取到。

一些具体的例子：

4 3 2 1 3  -->   排序是4 3 3 2 1
    ^   ^
  2和第二个3是逆序，所以必须交换

5 1 2 6 3 4 -->  排序是6 5 4 3 2 1
^     ^
  5 6是逆序的，所以要想取到5，就必须把6放到5的前面，然后就顺其自然了。

4 1 3 2 1 1 -->  4 3 2 1 1 1
  ^   这个一与2逆序，但我们无法将3 2同时放到前面，所以放弃

算法：

从大到小对 $a$ 排序，然后记 $a[i]$ 原来的位置为 $pos[i]$ 。

Step 1：首先寻找调整方案：

$a[0]$ 一定在 $ans$ 中。
从大到小，每次考虑下面两个数的位置 $pos[i]$ 和 $pos[j]$ ，且 $a[i] \geq a[j]$ 。
如果 $pos[i] < pos[j]$ ，则顺序正常，将 $a[j]$ 加到 $b$ 中，继续循环。
如果 $pos[i] > pos[j]$ ，则出现逆序，这时看是否能应用调整：
- XX 如果 $pos[i]$ 和 $pos[j]$ 中间没有比 $a[i]$ 大的数，则可以应用调整（将 $a[i]$ 调整到 $a[j]$ 前面，并将 $a[i]$ 加到 $b$ 中），跳出循环到 Step 2。
- 如果中间有比 $a[i]$ 大的数（例如： $3\ 5\ 4$ ，不能将 $4$ 调整到 $3$ 的前面），则不能调整，此时 $j++$ ，将这个 $a[j]$ 这个数放弃掉，这个例子里就是加入 $4$ ，但是放弃 $3$ 。

Step 2：一次调整用完后，我们一路贪心往后取数，能够往 $b$ 里加的加入，就得到答案了。

这里XX这一步需要 $O(1)/O(\log N)$ ：我们观察到如果 $pos[i]$ 和 $pos[j]$ 中有比 $a[i]$ 大的数，那么当前答案中的最后一个数肯定是在里面的，所以我们只要把上一次加到ans中的数的位置记下来，就可以判断了。

这样就是一个 $O(\log N)$ 的解法。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int t, n;
int a[200005];
pair<int, int> b[200005]; // value, position
#define f first
#define s second
vector<int> ans;
multiset<int> s;    // all values between pos[i] and pos[j]
 
bool cmp(pair<int, int> a, pair<int, int> b) {
  return a.f > b.f || (a.f == b.f && a.s < b.s);
}
 
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            b[i] = {a[i], i};
        }
        sort(b, b+n, cmp);
 
        // find the best place to apply the adjustment
        int i = 0, pos = b[0].s, lastpos = -1;
        ans.push_back(b[0].f);
        while (i < n-1) {
            bool next = false;
            for (int j = i+1; j < n; j++) {
                if (b[i].s > b[j].s) {   // found a reversed order
                  if (b[j].s > lastpos) {    // this is adjustable reversed order, add to ans and proceed to greedy
                    ans.push_back(b[j].f);
                    lastpos = pos;
                    pos = b[j].s;
                    i = j+1;            
                    goto greedy;
                  } else {                // not adjustable, skip j
                    continue;
                  }
                }
 
                // in order, add to ans
                ans.push_back(b[j].f);
                i=j;
                lastpos = pos;
                pos = b[j].s;
                next = true;
                break;
            }
            if (!next) break;
        }
 
        // greedily add the rest
greedy:
        for (; i < n; i++) {
          if (pos < b[i].s) {
            ans.push_back(b[i].f);
            pos = b[i].s;
          }
        }
 
        for (int i = 0; i < ans.size(); i++) {
            printf("%d%s", ans[i], i == ans.size()-1 ? "\n" : " ");
        }
        ans.clear();
        s.clear();
    }
    return 0;
}