专栏文章

题解：World Tour Finals 2025 Algorithm_a LIS Keeping Swaps

cchenxi2009
AT_awtf2025_a题解参与者 6已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@mioulege
此快照首次捕获于
2025/12/03 01:24
3 个月前
此快照最后确认于
2025/12/03 01:24
3 个月前
查看原文

思路

好像有些困难，不妨考虑一下什么时候可以交换 PiP_i 和 Pi+1P_{i+1}。
令 fif_i 为以 PiP_i 为开头的 LIS 长度，gig_i 为以 PiP_i 为结尾的 LIS 长度，mxl\text{mxl} 为 PP 的 LIS 长度。把逆序的两个数字交换不会减小 LIS 长度，只可能增加，并且增加后新的 LIS 一定经过 PiP_i 和 Pi+1P_{i+1}，即 fi+gi+1>mxlf_i+g_{i+1}>\text{mxl}，如果这个条件不满足，我们就可以交换 PiP_i 和 Pi+1P_{i+1}。
我们考虑一个 fi=mxlf_i=\text{mxl} 的位置，它的左边显然没有 Pj<PiP_j<P_i，不然 LIS 长度就不是 mxl\text{mxl} 了；那么肯定有 gi=1g_i=1，代入上面那个条件，发现只要 fi−1<mxlf_{i-1}<\text{mxl} 我们就可以把 Pi−1P_{i-1} 和 PiP_i 交换，因为每一个 fi=mxlf_i=\text{mxl} 的 PiP_i 都是前缀最小值，它们之间的顺序又不能互换，所以把所有这些 PiP_i 不改变顺序腾挪到 PP 的开头显然是字典序最小的。
然后除去开头这些元素之后剩下的元素是一个 mxl←mxl−1\text{mxl}\leftarrow\text{mxl}-1 后的一个子问题，重复上面的操作把 fi=mxlf_i=\text{mxl} 的所有位置挪到开头继续做就好了...吗？
我们观察第一组样例，发现上面推导的问题所在：mxl←mxl−1\text{mxl}\leftarrow\text{mxl}-1 之后 LIS 长度的限制并没有改变，也就是删去开头处理好的元素之后我们要处理的是一个 swap 限制变为 fi+gi+1≤mxl+1f_i+g_{i+1}\le\text{mxl}+1 的子问题，条件变得宽松了。
对于这个更宽松的问题，我们可以贪心地考虑当前序列中剩下的最小元素 PxP_x，显然有 gx=1/2g_x=1/2，并且任何其它元素的 gg 都是不小于 gxg_x 的，若 gx=1g_x=1，则它可以挪到当前序列的开头；否则若 gx=2g_x=2，则与 Px−1P_{x-1} 可以换位当且仅当 fx−1≤mxl−1f_{x-1}\le \text{mxl}-1，不能够自由移动。gx=1g_x=1 当且仅当 PxP_x 小于上一轮删除元素的最小值，若此条件被满足，则可以在开始下一轮移动之前将序列当前的最小元素移至 PP 开头。
继续考虑后续子问题，发现可以归纳为以下几步：
  • 从 mxl\text{mxl} 到 11 遍历 lenlen；
  • 将所有 fi=lenf_i=len 的未加入答案的元素按照从左往右的顺序加入答案；
  • 如果未加入答案的最小的 PiP_i 小于目前答案序列的最后一个元素，那么将其加入答案序列。
时间复杂度 O(∑Nlog⁡N)O(\sum N\log N)。

代码

CPP
#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;
}

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...