题解：World Tour Finals 2025 Algorithm_a LIS Keeping Swaps

· · 题解

思路

好像有些困难，不妨考虑一下什么时候可以交换 P_i 和 P_{i+1}。

令 f_i 为以 P_i 为开头的 LIS 长度，g_i 为以 P_i 为结尾的 LIS 长度，\text{mxl} 为 P 的 LIS 长度。把逆序的两个数字交换不会减小 LIS 长度，只可能增加，并且增加后新的 LIS 一定经过 P_i 和 P_{i+1}，即 f_i+g_{i+1}>\text{mxl}，如果这个条件不满足，我们就可以交换 P_i 和 P_{i+1}。

我们考虑一个 f_i=\text{mxl} 的位置，它的左边显然没有 P_j<P_i，不然 LIS 长度就不是 \text{mxl} 了；那么肯定有 g_i=1，代入上面那个条件，发现只要 f_{i-1}<\text{mxl} 我们就可以把 P_{i-1} 和 P_i 交换，因为每一个 f_i=\text{mxl} 的 P_i 都是前缀最小值，它们之间的顺序又不能互换，所以把所有这些 P_i 不改变顺序腾挪到 P 的开头显然是字典序最小的。

然后除去开头这些元素之后剩下的元素是一个 \text{mxl}\leftarrow\text{mxl}-1 后的一个子问题，重复上面的操作把 f_i=\text{mxl} 的所有位置挪到开头继续做就好了...吗？

我们观察第一组样例，发现上面推导的问题所在：\text{mxl}\leftarrow\text{mxl}-1 之后 LIS 长度的限制并没有改变，也就是删去开头处理好的元素之后我们要处理的是一个 swap 限制变为 f_i+g_{i+1}\le\text{mxl}+1 的子问题，条件变得宽松了。

对于这个更宽松的问题，我们可以贪心地考虑当前序列中剩下的最小元素 P_x，显然有 g_x=1/2，并且任何其它元素的 g 都是不小于 g_x 的，若 g_x=1，则它可以挪到当前序列的开头；否则若 g_x=2，则与 P_{x-1} 可以换位当且仅当 f_{x-1}\le \text{mxl}-1，不能够自由移动。g_x=1 当且仅当 P_x 小于上一轮删除元素的最小值，若此条件被满足，则可以在开始下一轮移动之前将序列当前的最小元素移至 P 开头。

继续考虑后续子问题，发现可以归纳为以下几步：

时间复杂度 O(\sum N\log N)。

代码

#include<bits/stdc++.h>
using namespace std;
#define ep emplace
#define eb emplace_back
#define ef emplace_front
#define ll long long
const int N = 300000;
int T,n,p[N],f[N],mxl,ans[N],ed,it;
pair<int,int> pr[N];
set<int>s;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> T;
    while(T --){
        cin >> n;
        for(int i = 1;i <= n;i ++) cin >> p[i];
        for(int i = 1;i <= n;i ++) f[i] = 0,s.ep(i);
        f[0] = 1e9,mxl = ed = 0,it = 1;
        for(int i = n;i;i --){
            int l = 0,r = n - i;
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(p[i] < f[mid]) l = mid;
                else r = mid - 1;
            }
            f[l + 1] = max(f[l + 1],p[i]),pr[i] = {l + 1,p[i]};
            mxl = max(mxl,l + 1);
        }
        sort(pr + 1,pr + n + 1),reverse(pr + 1,pr + n + 1);
        for(int i = mxl;i;i --){
            while(it <= n && pr[it].first >= i){
                int num = pr[it ++].second;
                if(!s.count(num)) continue;
                ans[++ ed] = num;
                s.erase(num);
            }
            if(s.size() && *s.begin() < ans[ed]){
                ans[++ ed] = *s.begin();
                s.erase(s.begin());
            }
        }
        for(int i = 1;i <= n;i ++) printf("%d ",ans[i]);
        printf("\n");
    }
    return 0;
}