题解：AT_awtf2025_a LIS Keeping Swaps

dyc2022 · 2026-06-17 17:04:21 · 题解

更好的阅读体验

我认为这个贪心策略并不显然。这篇题解的大部分篇幅都是证明。

在代码之前有太长不看版的本题结论。

既然题目要求在邻项交换的过程中序列的 LIS 长度保持不变，因此我们直接观察 LIS 在交换过程中的变化。

假设 f_i 表示以 i 开始的最长上升子序列的长度，同时记原序列的 LIS 长度为 l。我们假设可能成为 LIS 起点的位置 i_1 < i_2 < \cdots < i_k。显然，这些位置一定满足 p_{i_1} > p_{i_2} > \cdots > p_{i_k}，否则从 i_1 \sim i_k 开始的最长上升子序列的长度就不会相等。

那么有一个基础的观察，就是无论如何交换，p_{i_1}, p_{i_2}, \cdots, p_{i_k} 的相对先后顺序不会发生改变。原因是，假如 p_{i_x} 和 p_{i_y} 的相对先后顺序改变了，设 x < y，那么原本由 i_x 开始的上升子序列的开头又增加了 p_{i_y} 这个数，这会使排列的 LIS 长度增加 1，因此不符合题意。

接下来我们将要说明，将 p_{i_1}, p_{i_2}, \cdots, p_{i_k} 分别移动到 p 序列上下标为 1, 2, \cdots, k 的位置上，是不劣的。

假设相邻两个可能成为 LIS 起点的位置 i_x 和 i_{x+1}。则我们声称对于 \forall j \isin (i_x, i_x+1)，都有 p_j > p_{i_{x+1}}。

假设存在 p_j < p_{i_{x+1}}，那么以 j 开始的最长上升子序列可以包含 i_{x+1}，因此长度至少为 l+1。这和 l 是 LIS 长度相违背。

这意味着，由于 (i_x, i_{x+1}) 范围内都是 > p_{i_{x+1}} 的数字，因此将 i_{x+1} 移动到 i_x + 1 的位置会让字典序变小。同理，我们也可以说明将 i_1 移动到 1 的位置上，会让字典序变小。

因此，我们确定了答案的前 k 个数字分别是 p_{i_1} \sim p_{i_k}。接下来将给出一定能够达到这种状态的证明。

容易发现，要达到这种状态，只需要找到第一个可以往左交换的 i_x，然后交换 i_x - 1 和 i_x。

为什么交换 i_x - 1 和 i_x 一定不会让 LIS 长度增加？考虑我们要将 i_x 和 i_x - 1 进行交换，这里 i_x - 1 不应当是 i_1 \sim i_k 中的任何一个。假设以 i_x 为开头的最长上升子序列的下一个位置为 j。那么如果交换后 LIS 的长度增加，那么就说明 p_{i_x - 1} 可以插在 p_{i_x} 和 p_j 之间，也就是说 p_{i_x - 1} < p_j。在此情况下，i_x - 1 也能和 j 形成一个长度和以 i_x 开头的 LIS 相等的上升子序列，因此 i_x - 1 也是 LIS 的一个可能的起点，这和 i_x - 1 不属于 i_1 \sim i_k 矛盾。

因此每一步交换操作都是合法的，得证。

将 i_1 \sim i_k 移到序列最开头后，就变成了 LIS 长度 -1 的子问题了吗？其实并不是。我们发现，在一些情况下，将 i_1 \sim i_k 移动到开头后，我们还能将一些数字移动到还没确定的第一个位置，然后再转化为 LIS 长度 -1 的子问题。这里 LIS 长度 -1 的子问题指的是，将 f_j = l-1 的 j 移动到紧接着的若干个位置。

我们断言，在进行一次将所有 f_j 为一个相同值的 j 往左移动后，假设被确定的最后一个数字是 x，如果当前还未被确定的最小值 p_m 满足 p_m < x，则我们可以将 p_m 移动到第一个未被确定的位置。

接下来将举一例来方便理解。在本例中，所有红色数字表示已经被确定的位置。

此情况下 f_i = 5 的所有 i 都已经固定好。接下来需要将 f_i = 3 的 i = 5 往前移动，得到

接下来，未被确定的最小值 p_m = 4，而 x = 5，满足 p_m < x。因此我们可以将 4 往前移动，得到

“将所有 f_i 相同的 i 向前移动”这一步前面已经说明过了。接下来将会说明“选择未被确定的最小值 p_m，若 p_m < x 则将其向前移动”这一步有什么道理。

考虑归纳。首先先考虑 f_i = l 的 i_1 \sim i_k。当 p_{i_1} \sim p_{i_k} 已经被确定后，如果此时 1 未被选择，那么我们可以把 1 放到第 k+1 个位置。因为进行完这个操作后，此时 p_{k+2} \sim p_n 的 LIS 最多为 l-1，由于 1 比 p_{k+2} \sim p_n 内的所有数字都小，因此操作完以 1 开头的 LIS 长度至多为 l，满足题意。否则如果此时 1 已经被选了，那么由于已经满足 p_1 > p_2 > \cdots > p_k，因此 p_k = 1。这时如果要将一个比 p_{k+1} 更小的数字放到 k+1 的位置，那必然会导致 [p+1, n] 的 LIS 长度 +1；又因为 p_k = 1，因此会使 [k, n] 的 LIS 长度变成 l+1，不符合题意。

我们称“先将所有 f_j = l' 的 j 往左移动后，假设被确定的最后一个数字是 x，如果当前还未被确定的最小值 p_m 满足 p_m < x，则我们可以将 p_m 移动到第一个未被确定的位置”为一次操作。那么容易发现，p 中已经被确定的部分可以分成若干个连续段，一个连续段就代表在同一次操作。

我们会发现，对于一个已经确定的连续段，这个连续段的最小值应该会大于前一段的最小值。因为假如这一段的最小值 < 前一段的最小值，那么由于我们的贪心策略，这一段的最小值应该会在前一段被选完的时候直接被推到前面。

这说明，该段的最小值 > 前一段的最小值，又 > 前两段的最小值，……，> 第一段的最小值。这就意味着，在这种策略下，每一段的最小值都在原序列的一个 LIS 上！

那么我们假设要推到前面的数字 > 我们目前已经确定的最后一个数字（记为 x）。容易发现，此时未被确定部分的 LIS 长度是 l' - 1。假设未被确定部分的最小值为 p_m。

1. 存在 t < m 使得 f_t = l' - 1，即 m 的左边有可能成为最长上升子序列起点的点，如图。

   那么由于 p_m 是未被确定的最小的数，因此 p_m < p_t，即此时将 p_m 移动到前面后，p_m 变成了一个长度为 l' 的上升子序列的起点，如图中蓝色圈起的部分。又因为 p_m > x，而 x 此时已经在一个长度为 l 的原序列 LIS 中，因此这个操作将会使原序列的 LIS 长度 +1，不符合题意。

2. 不存在 t < m 使得 f_t = l' - 1，即 m 的左边没有可能成为最长上升子序列起点的点。

   那么在此情况下，由于 p_m 最小，且 m 左侧没有其他的最长上升子序列起点，因此 p_m 一定是一个最长上升子序列起点。虽然此情况下 p_m 可以被移动到下一个未被确定的位置，但我们可以禁止这种操作，原因是当 l' \leftarrow l' - 1，p_m 就会随着所有 f_j = l' - 1 的 j 被推到左边了。

至此，我们说明了“若 p_m < 已经确定的最后一个数，就将 p_m 移动到最左边”这个操作的正确性。

综上本题就得到了一个非常简洁的做法！

• 求出以 i 开头的 LIS 长度 f_i，令原序列 LIS 长度为 l。
• 对于 i = l \to 1，执行以下两种操作：
  • 将所有未被确定的 f_j = i 的 j，按照 j 从小到大的顺序推到未被确定的最左边。
  • 查看当前未被确定的最小值 p_m。若 p_m < 我们已经确定的最后一个数，则将 p_m 移动到未被确定的最左边。

只要求出 f 数组，问题就能得到解决。而这是容易的。

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

#include<bits/stdc++.h>
#define endl '\n'
#define N 250006
using namespace std;
inline void chkmin(int &x,int y) {x=x<y?x:y;}
inline void chkmax(int &x,int y) {x=x<y?y:x;}
int n,mx,a[N],f[N],vis[N];
vector<int> vec[N];
struct BIT {
  int tree[N];
  void init() {for(int i=1;i<=n;i++)tree[i]=0;}
  void update(int k,int x) {for(;k;k-=k&-k)chkmax(tree[k],x);}
  int query(int k)
  {
    int ret=0;
    for(;k<=n;k+=k&-k)chkmax(ret,tree[k]);
    return ret;
  }
} T;
void solve()
{
  scanf("%d",&n),mx=0;
  for(int i=1;i<=n;i++)
    scanf("%d",&a[i]),vec[i].clear(),vis[i]=0;
  T.init();
  for(int i=n;i;i--)
  {
    f[i]=T.query(a[i]+1)+1,T.update(a[i],f[i]);
    vec[f[i]].push_back(i),chkmax(mx,f[i]);
  }
  for(int i=1;i<=n;i++)
    reverse(vec[i].begin(),vec[i].end());
  int now=1,lst=0;
  for(int i=mx;i;i--)
  {
    for(int j:vec[i])
      if(!vis[a[j]])printf("%d ",a[j]),vis[lst=a[j]]=1;
    while(now<=n&&vis[now])now++;
    if(now<lst)printf("%d ",now),vis[lst=now]=1;
  }
  putchar(10);
}
main()
{
  int T; scanf("%d",&T);
  while(T--)solve();
  return 0;
}