526互联

Atcoder Regular Contest 114 F - Permutation Division

发布时间 2023-07-14 12:13:19作者: tzc_wk

显然分成 \(k\) 段以后，最大化形成的排列的字典序的策略是将所有段按第一个元素的大小降序排列。

由于最终排列的字典序肯定 \(\ge\) 原排列的字典序，因此我们考虑最大化最终排列与原排列的 LCP，这部分就考虑二分答案，记 \(dp_i\) 表示以 \(p_1\) 开始 \(p_i\) 结尾的 LDS 的长度，那么考虑枚举 \(mid\) 所在的段的开始元素 \(i\)，那么后面我们肯定会选最小的 \(k-dp_i\) 个元素，判断后面第 \(k-dp_i\) 大的数是否 \(\le p_i\) 即可。

最大化完 LCP 之后，由于我要让后面的段的第一个元素尽可能小，所以我们挑选前面 \(dp_i\) 最大的位置就行了。总复杂度 \(O(n\log n)\)。

const int MAXN=2e5;
const int INF=0x3f3f3f3f;
int n,k,a[MAXN+5],dp[MAXN+5],t[MAXN+5],vis[MAXN+5];
void add(int x,int v){for(int i=x;i;i-=(i&(-i)))chkmax(t[i],v);}
int query(int x){int ret=-INF;for(int i=x;i<=n;i+=(i&(-i)))chkmax(ret,t[i]);return ret;}
bool check(int mid){
	vector<int>vec;
	for(int i=mid+1;i<=n;i++)vec.pb(a[i]);
	sort(vec.begin(),vec.end());
	for(int i=1;i<=mid;i++)if(k-dp[i]<=vec.size()&&vec[k-dp[i]-1]<a[i])return 1;
	return 0;
}
int main(){
	scanf("%d%d",&n,&k);memset(t,192,sizeof(t));
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	dp[1]=1;add(a[1],1);
	for(int i=2;i<=n;i++)dp[i]=query(a[i])+1,add(a[i],dp[i]);
	for(int i=1;i<=n;i++)if(dp[i]>=k){
		for(int j=1;j<=n;j++)printf("%d%c",a[j]," \n"[j==n]);
		return 0;
	}
	int l=1,r=n-1,p=0;
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid))p=mid,l=mid+1;
		else r=mid-1;
	}
	for(int i=1;i<=p;i++)printf("%d ",a[i]);
	int mn=k;vector<pii>vec;
	for(int i=p+1;i<=n;i++)vec.pb(mp(a[i],i));
	sort(vec.begin(),vec.end());
	for(int i=1;i<=p;i++)if(k-dp[i]<=vec.size()&&vec[k-dp[i]-1].fi<a[i])chkmin(mn,k-dp[i]);
	for(int i=0;i<mn;i++)vis[vec[i].se]=1;vis[n+1]=1;
	int cur=p+1;while(!vis[cur])printf("%d ",a[cur]),++cur;
	for(int i=mn-1;~i;i--){
		int pos=vec[i].se+1;
		while(!vis[pos])++pos;
		for(int j=vec[i].se;j<pos;j++)printf("%d ",a[j]);
	}printf("\n");
	return 0;
}