我们考察什么样的点会决定一个序列的合法性。

我们断言：从第一个数往后跳 nxt（下一个比其小的位置），提取一列位置，只有这些位置上 $p_i-i\le k$ 是能使我们倒闭（不合法）的，正确性显然。

这就是要求提取的一列位置两两距离不大于 $k$。

（以下没有正确性保证）

我们首先声称一个数如果在原序列上不是能使我们倒闭的，我们不会记其为交换时的 $y$。

我们接着声称一个数作为 $y$，$x$ 必然在提取出的序列中上一个位置的后面。

据此，我们发现能重分配两个相邻的距离。

我们声称当只有一个距离 $> k$，且其与其后距离值之和 $\le 2k$ 时合法。

但如下数据（TC 98）会使其倒闭：

8 3
8 8 8 8 8 8 5 7

故我们接着声称：当只有一个距离 $>k$，且后面有一个数比其小，且不为选出的序列中的数时，则合法。

这可以通过本题：

#include<bits/stdc++.h>

int n,k;
int a[500005];
int s[500005],tp;
int nxt[500005];
int sz[500005],cc;
int vis[500005];
int pos[500005];
int tag=0;

int main(){
	std::ios::sync_with_stdio(false);
	
	std::cin>>n>>k;
	for(int i=1;i<=n;i++) std::cin>>a[i];
	for(int i=1;i<=n;i++){
		while(tp){
			if(a[s[tp]]<=a[i]) break;
			nxt[s[tp--]]=i;
		}
		s[++tp]=i;
	}
	while(tp){
		nxt[s[tp--]]=n+1;
	}
	for(int j=1;j<=n;j=nxt[j]){
		sz[++cc]=nxt[j]-j;
		pos[cc]=j;
		vis[j]=1;
	}
	
	int ans=0;
	for(int j=1;j<=cc;j++){
		if(sz[j]>k) ans++;
	}
	if(!ans) puts("YES");
	else if(ans>=2||(ans==1&&cc==1)) puts("NO");
	else{
		for(int j=1;j<=(cc-1);j++){
			if(sz[j]>k) tag=j;
			if(sz[j]>k&&sz[j+1]<k&&(sz[j]+sz[j+1])<=2*k){
				puts("YES");
				return 0;
			}
		}
		if(sz[tag]>2*k) puts("NO");
		else{
			for(int j=pos[tag];j<=n;j++){
				if(a[j]<a[pos[tag]]&&(!vis[j])){
					puts("YES");
					return 0; 
				}
			}
			puts("NO");
		}
	}
	
	return 0;
}

passed 记录见：

https://codeforces.com/contest/887/submission/294909520