AtCoder-arc114_f

@wsyear强无敌，模拟赛场切黑题。

题目大意

给你一个长度为 $n$ 的排列，Alice 先会把它分成 $m$ 段。

然后 Bob 会把这 $m$ 段重新排列，而每段内部位置不变。

Alice 希望这个序列字典序最小，而 Bob 希望这个序列字典序最大。

输出重排后的序列。

解题思路

考虑贪心。

我们发现字典序一定不会比原来的序列小，所以我们要让不变的前缀尽量长。

很明显这个前缀的长度是有单调性的，所以可以考虑二分。

判断是否可行：

假设你现在二分到的长度是 $len$。

我们分的 $m$ 段中有两种，一种是在 $[1,len]$ 中的，一种是在 $[len+1,n]$ 中的。

对于在 $[1,len]$ 中的段，我们发现他们的开头是单调递减的，否则Bob可以把开头较大的移动到前面。

对于 $[len+1,n]$ 的段，每一段的开头都要比 $[1,len]$ 中的开头小，否则你可以把开头大的移到前面。

考虑枚举 $[1,len]$ 中的段数 $x$，然后求出最后一段开头的最大值 $val$，那么只要找出 $[len+1,n]$ 中有多少个数（假设有 $y$ 个）可以作为开头（也就是小于 $val$），如果 $x+y\ge m$ 那么就可行。

接下来要求出 $val$：

这里的思路参考了 P4577 [FJOI2018]领导集团问题 的思路。

维护一个set，从大到小排，其中第 $i$ 个元素表示长度为 $i$ 的递减子序列的最大结尾。

考虑加入一个数 $x$，那么找到他的后继 $y$，发现以 $x$ 结尾和以 $y$ 结尾的最长下降子序列长度是一样的，而 $x<y$，所以可以把 $y$ 删除。

现在求出了最长的不变的前缀 $len$，我们现在就只要考虑 $[len+1,n]$ 应该怎么分比较好。

首先你在 $[len+1,n]$ 分的段数一定是越少越好的，而这个段数在check的时候就可以求出来了。

显然你要取最小的前几个一定是最优的，这样才能保证重排后 $len+1$ 的位置数最小。

这样就做完了。

代码示例

不是很清除，凑和着看吧：

/*
* @Author: ftt2333
* @Email: ftt2333@126.com
* @Last Modified time: 2022-11-10 10:50:00
*/

#include <bits/stdc++.h>
using namespace std;
#define off ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fin(s) freopen(s, "r", stdin)
#define fout(s) freopen(s, "w", stdout)
#define fio(s) fin(s".in"), fout(s".out")
using ll = long long; using ull = uint64_t;
using lll = __int128; using ulll = __uint128_t;
using db = double; using ldb = long double;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using vi = vector<int>; using vl = vector<ll>;
using uchar = unsigned char; using uint = unsigned int;
template<class T> using uid = uniform_int_distribution<T>;
template<class T> using urd = uniform_real_distribution<T>;
#define rep(i, a, b) for(auto i = (a); i <= (b); i++)
#define per(i, a, b) for(auto i = (a); i >= (b); i--)
#define go(i, h, e, x) for(int i = h[x]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define szof(a) ((int)(a).size())
#define mem(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))

mt19937 rnd(random_device{}());
const int mod = 998244353, N = 2e5 + 10;
int a[N], n, m, sum[N], id[N];
bool vis[N];

int check(int len) {
  set<int> s;
  rep(i, 1, len) {
    if(a[i] > a[1]) continue;
    auto it = s.upper_bound(a[i]);
    if(it != s.begin()) s.erase(--it);
    s.insert(a[i]);
  }
  rep(i, 1, n) sum[i] = 0;
  rep(i, len + 1, n) sum[a[i]]++;
  rep(i, 2, n) sum[i] += sum[i - 1];
  int j = szof(s);
  for(auto x: s) {
    if(j + sum[x] >= m) return j;
    j--;
  }
  return 0;
}

int main() {
  off;
  cin >> n >> m; rep(i, 1, n) cin >> a[i], id[a[i]] = i;
  int l = 0, r = n;
  for(; l < r; ) {
    int mid = l + r + 1 >> 1;
    if(check(mid)) l = mid;
    else r =  mid - 1;
  }
  int res = m - check(l);
  vi heads; heads.pb(1);
  if(1 > l) res--;
  rep(i, 1, n) if(res && id[i] != 1 && id[i] > l) heads.pb(id[i]), res--;
  sort(all(heads), [&](int x, int y) {
    return a[x] > a[y];
  });
  for(int x: heads) vis[x] = 1;
  for(int x: heads) {
    cout << a[x] << ' ';
    int i = x + 1;
    for(; i <= n && !vis[i]; i++) cout << a[i] << ' ';
  }
}