AT_arc114_f

提示，下文中有较多变量名重复，请注意自行理解。

其实一步一步做还是感觉不难的，可能这就是 ARC 吧。（

先手玩一下，看看两边会如何操作。首先，设分成第 $i$ 个段的第 $j$ 位为 $b_{i,j}$，那么对方肯定会贪心地把 $b_{i,1}$ 最大的 $i$ 段给放到开头，而所有的 $b_{i,1}$ 不相同，所以设最后对方放的第 $i$ 个段的第 $j$ 位为 $c_{i,j}$，则 $c_{1,1}\ge k$。所以我方就要贪心地，使 $b_{i,1}$ 取到当前剩下的最小的 $k$ 个数。

但是不一定能取到，因为会发现，如果当前 $a_1=x$，则一定存在一个 $b_{i,1}=x$。若此 $x$ 比剩下最小的 $k$ 个数中最大的还大，则一定有 $c_{1,1}=x$，剩下的 $c_{i,1}$ 依次为剩下最小的 $k-1$ 个数。

并且还有一个性质，就是答案的字典序不会比原序列小，否则对方就直接不操作。

分析出来这些就考虑怎么一段一段取，每取一段变成一个子问题。设上面两种情况分别为情况一和二，容易发现，如果出现上面的第一种情况，则剩下序列的开头位置字典序一定会变小。于是贪心地，我们就要尽可能使用情况二，剩下不能为情况二的再用一。

再来分析一下如何能取到情况二。设当前段开头为 $x$，下一段开头在 $i$ 取 $y$，还要取 $k$ 段。首先有 $x>y$，否则对方会选择把 $y$ 换到前面。并且有 $\sum_{j>i}[a_j<y]\ge k$，否则剩下的一定会有段头 $>y$ 的。

然后还需要做一个观察：如果确定了 $y$，那么 $y$ 之前取的组的数量越多越好。这是因为，根据上面的结论，若剩下还没取的有 $k$ 段，则下一个组的段头就是剩下数中第 $k$ 小的，显然 $k$ 越小越好。同时，我们现在只确定了 $y$，没有确定段的右端点。但也容易发现，这个右端点越大越好。这是因为设下一段开头位置为 $p$，则 $p$ 位置的字典序一定发生变化，于是这个位置越往后越好。

此时就可以开始处理了。首先对于 $x>y$ 的条件，又是越多越好且没有其他限制，于是发现，令情况二最后一段的段头位置为 $i$，则情况二取到的段数就是，钦定开头为 $a_1$，结尾为 $a_i$ 的最长下降子序列长度。找完 $i$ 后要找情况一的第一段的段头，设还要取 $k$ 段，这个位置就是最大的 $j$，满足 $\sum_{l>j}[a_l<a_i]\ge k$。

于是就依次维护这两部分。第一部分显然简单 SGT 维护。第二部分，将第一部分处理出来的每个 $i$ 和 $k$ 离线下来，考虑按照 $a_i$ 从小到大排序，依次标记每个位置 $a_i$ 的位置为 $1$，SGT 上二分找到最后一个后缀和 $\ge k$ 的位置 $p$，若 $p>i$ 则更新答案。令答案为一个二元组 $(x,y)$ 表示 $[x,n]$ 的分段用情况一，还要分 $y$ 段。于是最后答案就是在 $x$ 最大的基础上，使 $y$ 尽可能小的 $(x,y)$。最后输出答案就直接输出 $[1,x-1]$ 的 $a_i$ 以及对 $[x,n]$ 做情况一的结果即可。时间复杂度 $O(n\log n)$，结束。

code：

int n,m,a[N],b[N],p[N],dp[N];
vector<pii> g[N];
struct SGT{
	int tr[N<<2];
	il void up(int u){
		tr[u]=max(tr[u<<1],tr[u<<1|1]);
	}
	void upd(int l,int r,int u,int x,int y){
		if(l==r){
			tr[u]=y;
			return;
		}
		int mid=(l+r)>>1;
		if(x<=mid){
			upd(l,mid,u<<1,x,y);
		}else{
			upd(mid+1,r,u<<1|1,x,y);
		}
		up(u);
	}
	int qry(int l,int r,int u,int x,int y){
		if(r<x||l>y){
			return 0;
		}
		if(l>=x&&r<=y){
			return tr[u];
		}
		int mid=(l+r)>>1;
		return max(qry(l,mid,u<<1,x,y),qry(mid+1,r,u<<1|1,x,y));
	}
}T;
struct Sgt{
	int tr[N<<2];
	il void up(int u){
		tr[u]=tr[u<<1]+tr[u<<1|1];
	}
	void upd(int l,int r,int u,int x){
		if(l==r){
			tr[u]++;
			return;
		}
		int mid=(l+r)>>1;
		if(x<=mid){
			upd(l,mid,u<<1,x);
		}else{
			upd(mid+1,r,u<<1|1,x);
		}
		up(u);
	}
	int qry(int l,int r,int u,int k){
		if(l==r){
			if(k==1&&tr[u]){
				return l;
			}
			return 0;
		}
		int mid=(l+r)>>1;
		if(tr[u<<1|1]>=k){
			return qry(mid+1,r,u<<1|1,k);
		}
		return qry(l,mid,u<<1,k-tr[u<<1|1]);
	}
}R;
void Yorushika(){
	read(n,m);
	rep(i,1,n){
		read(a[i]);
		p[a[i]]=i;
	}
	rep(i,1,n){
		if(i==1){
			dp[i]=0;
		}else{
			dp[i]=T.qry(1,n,1,a[i]+1,n);
		}
		if(!dp[i]&&i>1){
			continue;
		}
		T.upd(1,n,1,a[i],++dp[i]);
		if(dp[i]>=m){
			rep(i,1,n){
				printf("%d ",a[i]);
			}
			return;
		}
		g[a[i]-1].eb(m-dp[i],i);
	}
	int x=1,y=m;
	rep(i,1,n){
		R.upd(1,n,1,p[i]);
		for(auto [k,j]:g[i]){
			int p=R.qry(1,n,1,k);
			if(p>j){
				if(p>x){
					x=p,y=k;
				}else if(k<y){
					y=k;
				}
			}
		}
	}
	rep(i,1,x-1){
		printf("%d ",a[i]);
	}
	rep(i,1,n){
		b[i]=a[i];
	}
	sort(b+x,b+n+1);
	drep(i,x+y-1,x){
		printf("%d ",b[i]);
		for(int j=p[b[i]]+1;j<=n&&a[j]>b[x+y-1];j++){
			printf("%d ",a[j]);
		}
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}

感觉代码还是挺清楚 desu~