令 \(a\) 为题目中的 \(P\)。
首先考虑后手的重排策略是什么。
因为 \(a\) 是个排列，元素互不相同，那么肯定就是按照每一段的第一个数的大小，越大的放在越前面。
那么当 \(a_1\le k\) 的时候，显然先手会把以 \(1\sim k\) 开头来划分段。
因为否则存在一个开头 \(> k\) 的段，后手把其放在最前面，那么此时得到的新排列肯定开头 \(> k\)；一定不比上面提到的划分方式（开头为 \(k\)）优。
接下来考虑 \(a_1 > k\) 的时候。
类似的，可以知道肯定不会有划分出的段的开头 \(> a_1\)，因为这样肯定不如就让 \(a_1\) 开头。
所以说每段开头都 \(\le a_1\)。
那么考虑 \(a_1\) 所在的段 \([1, w]\)，同时肯定就会有一个以 \(w + 1\) 开头的段。
按照后手的重排策略，最终得到的排列 \(a'\) 肯定满足 \(a_{[1, w]} = a'_{[1, w]}, a'_{w + 1}\ge a_{w + 1}\)。
于是能够发现要使的最后得到的 \(a'\) 尽量小，就需要最大化 \(\operatorname{LCP}(a, a')\)，其次如果最大化了 \(\operatorname{LCP} = w\)，就需要最小化 \([w + 1, n]\) 选出的段的开头按从大到小的顺序后的字典序。
先来考虑最大化 \(\operatorname{LCP}\)。
考虑枚举 \(\operatorname{LCP}\) 中的最后一段，记开头为 \(i\)。
考虑如果选出了 \(a_{j_1} > a_{j_2} > \cdots > a_{j_m}(1 = j_1 > j_2 > \cdots > j_m = i)\)，那么以 \(j_{1\sim k}\) 都成为段的开头，一定是不会影响最终的顺序的。
那么就还需要在 \([i + 1, n]\) 确定出 \(k - m\) 个开头，因为要最大化 \(\operatorname{LCP}\)，所以显然会去选最后的 \(k - m\) 个 \(< a_i\) 的数（当然需要满足这些数的位置 \(> i\)）。
于是就可以知道需要最大化这个 \(m\)。
那么对 \(a\) 跑一个以 \(a_1\) 开头的最长下降子序列即可求出对于每个 \(i\) 的 \(m\)。
接下来考虑最小化 \([w + 1, n]\) 选出的段的开头按从大到小的顺序后的字典序。
根据上文提到的，可以知道，\(w + 1\) 后选择的开头就是 \(k - m\) 个 \(< a_i\) 的数。
又因为最大化了 \(\operatorname{LCP}\)，所以此时最后肯定会更好剩下 \(k - m\) 个数，所以说这 \(k - m\) 个数一定是 \([w + 1, n]\) 中最小的 \(k - m\) 个数。
那么最小化 \(k - m\) 就可以了。
对于上述找到第 \(k - m\) 个 \(< a_i\) 的数，可以考虑树状数组二分得到。
知道开头后，按照后手的方案构造即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
#include<bits/stdc++.h>
const int maxn = 2e5 + 10, limn = 1 << 18;
int a[maxn], w[maxn];
int f[maxn], val[maxn];
int ed[maxn];
int tr[limn + 1];
inline void add(int x) {
for (int i = x; i <= limn; i += i & -i)
tr[i]++;
}
inline int qry(int k) {
int now = limn;
for (int i = 17; ~ i; i--)
if (k > tr[now - (1 << i)])
k -= tr[now - (1 << i)];
else
now -= 1 << i;
return now;
}
int main() {
int n, k; scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]), w[a[i]] = i;
ed[n + 1] = 1;
if (a[1] <= k) {
for (int i = 1; i <= k; i++)
ed[w[i]] = 1;
for (int i = k; i; i--) {
printf("%d ", i);
for (int j = w[i] + 1; ! ed[j]; j++)
printf("%d ", a[j]);
}
return 0;
}
int mx = 0;
for (int i = 1; i <= n; i++) {
if (a[i] > a[1])
continue;
f[i] = std::upper_bound(val + 1, val + n + 1, a[i], std::greater<int>()) - val;
val[f[i]] = a[i];
mx = std::max(mx, f[i]);
}
if (mx >= k) {
for (int i = 1; i <= n; i++)
printf("%d ", a[i]);
return 0;
}
int lcp = 0, cnt = 0;
for (int i = 1; i <= a[1]; i++) {
int p = w[i], c = k - f[p];
if (c < i) {
int q = qry(i - c);
if (q > p) {
if (q > lcp) lcp = q, cnt = k + 1;
if (q == lcp && c < cnt) cnt = c;
}
}
add(p);
}
for (int i = 1; i < lcp; i++)
printf("%d ", a[i]);
std::vector<int> b;
for (int i = lcp; i <= n; i++)
b.push_back(i);
std::sort(b.begin(), b.end(), [&](int x, int y) {return a[x] < a[y];});
for (int i = 0; i < cnt; i++)
ed[b[i]] = 1;
for (int i = cnt - 1; ~ i; i--) {
printf("%d ", a[b[i]]);
for (int j = b[i] + 1; ! ed[j]; j++)
printf("%d ",a[j]);
}
return 0;
}