2026牛客暑期多校 7——Problem D. 天下第一武道会（要多手摸样例啊，然后猜测一些结论啊，想一想样例为什么做出这样的选择）（不想要卡死=尽量晚卡死啊 / 所谓的让区间最大，就是找到最大的右端点）

题目大意

这是一份为您整理好的整洁、规范的中文题面，去除了杂乱的内容且未包含任何解题思路：

题目描述：天下一武道会 (Tenkaichi Budōkai)

时间限制： C/C++/Rust/Pascal 1秒，其他语言2秒

空间限制： C/C++/Rust/Pascal 1024 MB，其他语言2048 MB

特殊判定 (Special Judge)： 是，64位整数输入输出格式：%lld

天下一武道会汇聚了来自世界各地的 $n$ 名武术家。武术家们的编号为 $1, 2, \ldots, n$。

在比赛开始前，两名官员分别提交了固定的优先级列表 $P$ 和 $Q$。每个列表都恰好包含每位武术家一次，尽管武术家在两个列表中的排列顺序可能不同。

初始时，列表为：

$$P = (p_1, p_2, \ldots, p_n)$$

$$Q = (q_1, q_2, \ldots, q_n)$$

其中这两个序列都是 $1, 2, \ldots, n$ 的排列。一旦提交，两个列表的顺序都不允许被重新排列。

比赛委员会使用以下规则来模拟比赛。只要至少还有两名武术家剩余，就可以进行一场比赛：

设 $u$ 和 $v$ 分别为当前列表 $P$ 和 $Q$ 中排在最前面的未被淘汰的武术家。

• 如果 $u = v$，说明两位官员提名了同一位武术家。由于武术家不能与自己对战，且任何一位官员都不能跳过他们列表中的第一位武术家，此时模拟过程将陷入停滞状态，无法继续进行后续比赛。

• 否则（即 $u \neq v$），$u$ 和 $v$ 将进行对决。在模拟中，可以从 $\{u, v\}$ 中任意选择一名武术家 $z$ 作为败者。武术家 $z$ 将被淘汰出局，他也会同时从 $P$ 和 $Q$ 两个列表中被移除。移除后，每个列表中剩余武术家的相对顺序保持不变。

经过恰好 $n-1$ 场成功的比赛后，最终将只剩下一名武术家。这名武术家将被宣布为天下一武道会的冠军。

现在，你支持武术家 $x$。请判断：是否存在一种合法的比赛胜负序列，使得整个模拟过程永远不会陷入停滞状态，并且武术家 $x$ 最终成为冠军？

如果存在这样的序列，请输出任意一个符合条件的被淘汰武术家序列。

输入格式

第一行包含两个整数 $n$ 和 $x$（$2 \le n \le 2\times 10^5$，$1 \le x \le n$），分别表示武术家的数量和你希望成为冠军的武术家编号。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$。保证序列 $P$ 是 $1, 2, \ldots, n$ 的一个排列。

第三行包含 $n$ 个整数 $q_1, q_2, \ldots, q_n$。保证序列 $Q$ 是 $1, 2, \ldots, n$ 的一个排列。

输出格式

如果在不陷入停滞状态的前提下，无法使武术家 $x$ 成为冠军，请输出一行 NO。

否则，第一行输出 YES。

第二行输出 $n-1$ 个整数 $z_1, z_2, \ldots, z_{n-1}$，其中 $z_i$ 表示在第 $i$ 场比赛中被淘汰的武术家。

注意：

在进行第 $i$ 场比赛前，设 $u_i$ 和 $v_i$ 分别为 $P$ 和 $Q$ 中剩余排在最前面的武术家。你的输出必须满足 $u_i \neq v_i$ 且 $z_i \in \{u_i, v_i\}$。在执行完全部的 $n-1$ 场淘汰操作后，剩余的唯一武术家必须是 $x$。

如果存在多个符合条件的淘汰序列，输出其中任意一个均视为正确。

样例

样例 1

输入：

Plaintext

3 3
2 3 1
3 1 2

输出：

Plaintext

NO

样例 2

输入：

Plaintext

3 1
2 1 3
3 2 1

输出：

Plaintext

YES
2 3

样例 3

输入：

Plaintext

5 1
2 4 3 1 5
4 3 5 2 1

输出：

Plaintext

YES
4 3 2 5

样例解释

下面是对 样例 3 输出的详细解释：

初始时，$P$ 和 $Q$ 中剩余排在最前面的武术家分别是 2 和 4。他们进行对决，武术家 4 被淘汰。列表更新为：

$$P = (2, 3, 1, 5)$$

$$Q = (3, 5, 2, 1)$$

下一场比赛在武术家 2 和 3 之间进行。武术家 3 被淘汰，列表更新为：

$$P = (2, 1, 5)$$

接下来，被提名的武术家是 2 和 5。武术家 2 被淘汰，此时：

$$P = (1, 5)$$

$$Q = (5, 1)$$

最后，武术家 1 和 5 面对面进行对决，武术家 5 被淘汰。两个列表现在都只剩下武术家 1。

因此，模拟过程从未陷入停滞，武术家 1 成功成为了天下一武道会的冠军。

思路讲解

不想要卡死=尽量晚卡死啊

那么维护这样子的一个距离啊，可以使用这个 pbds。

int choose_p_or_q() {
	if (aliveP.empty() || aliveQ.empty()) {
		return -1;
	}
	auto [pid,qid] = make_tuple(*aliveP.begin(), *aliveQ.begin());
	ll pval = P[pid];
	ll qval = Q[qid];
	if (pval == qval) {
		return -1;
	}
	ll disp = aliveQ.order_of_key(valToQPos[pval]);
	ll disq = aliveP.order_of_key(valToPPos[qval]);
	auto erase_q = [&]() {
		++ans_idx;
		Ans[ans_idx] = Q[qid];
		aliveQ.erase(qid);
		aliveP.erase(valToPPos[qval]);
	};
	auto erase_p = [&]() {
		++ans_idx;
		Ans[ans_idx] = P[pid];
		aliveP.erase(pid);
		aliveQ.erase(valToQPos[pval]);
	};
	if (pval == X) {
		erase_q();
	} else if (qval == X) {
		erase_p();
	} else if (disp >= disq) {
		erase_q();
	} else {
		erase_p();
	}
	return 0;
}

不断反复调用 choose_p_or_q()，即可啊。

while (SZ(aliveP) >= 2 || SZ(aliveQ) >= 2) {
	int res = choose_p_or_q();
	if (res == -1) {
		cout << "NO\n";
		return;
	}
}
cout << "YES\n";
for (int i = 1; i <= ans_idx; ++i) {
	cout << Ans[i] << " ";
}

AC代码

AC
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84410045

源代码

// teamname: Gospel_rock
/**
 * Problem: Tenkaichi Budōkai
 * Contest: 
 * Judge: NowCoder
 * URL: https://ac.nowcoder.com/acm/contest/133882/D
 * Created: 2026-08-08 01:42:06
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define fsp(x) fixed << setprecision(x)
#define debug(x) cerr << "[" << #x << "]" << ": " << x << "\n"
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);

ll lT, testcase;

/*
 *
 */

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree<T, null_type, less<>, rb_tree_tag,
	tree_order_statistics_node_update>;

ll N, X;
int P[MAXN], Q[MAXN], valToQPos[MAXN], valToPPos[MAXN];
ll ans_idx = 0;
ll Ans[MAXN];
ordered_set<ll> aliveP;
ordered_set<ll> aliveQ;


void init() {
	ans_idx = 0;
	aliveP.clear();
	aliveQ.clear();
}

int choose_p_or_q() {
	if (aliveP.empty() || aliveQ.empty()) {
#ifdef LOCAL
		cerr << "aliveP:" << SZ(aliveP) << " aliveQ:" << SZ(aliveQ) << "\n";
#endif
		return -1;
	}
	auto [pid,qid] = make_tuple(*aliveP.begin(), *aliveQ.begin());
	ll pval = P[pid];
	ll qval = Q[qid];
	if (pval == qval) {
		return -1;
	}
	ll disp = aliveQ.order_of_key(valToQPos[pval]);
	ll disq = aliveP.order_of_key(valToPPos[qval]);
	auto erase_q = [&]() {
		++ans_idx;
		Ans[ans_idx] = Q[qid];
		aliveQ.erase(qid);
		aliveP.erase(valToPPos[qval]);
	};
	auto erase_p = [&]() {
		++ans_idx;
		Ans[ans_idx] = P[pid];
		aliveP.erase(pid);
		aliveQ.erase(valToQPos[pval]);
	};
	if (pval == X) {
		erase_q();
	} else if (qval == X) {
		erase_p();
	} else if (disp >= disq) {
		erase_q();
	} else {
		erase_p();
	}
	return 0;
}

void Solve() {
	cin >> N >> X;
	init();
	for (int i = 1; i <= N; ++i) {
		cin >> P[i];
		valToPPos[P[i]] = i;
		aliveP.insert(i);
	}
	for (int i = 1; i <= N; ++i) {
		cin >> Q[i];
		valToQPos[Q[i]] = i;
		aliveQ.insert(i);
		// valToQPos.set(Q[i],i);
	}
	while (SZ(aliveP) >= 2 || SZ(aliveQ) >= 2) {
		int res = choose_p_or_q();
		if (res == -1) {
			cout << "NO\n";
			return;
		}
	}
	cout << "YES\n";
	for (int i = 1; i <= ans_idx; ++i) {
		cout << Ans[i] << " ";
	}
	cout << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	// cin >> lT;
	// for (testcase = 1; testcase <= lT; ++testcase)
	Solve();
	return 0;
}

/*
AC
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84410045

*/

心路历程（WA，TLE，MLE……）