[R58C]猴子排序 - 代码源竞赛平台

时空限制

1S/512M

题目描述

jiangly 在玩一款叫做“猴子排序”的小游戏。

游戏规则如下：

• 初始时，系统会给定一个长度为 $n$ 的排列$^{\dagger}$ $P$。
• 接下来有 $m$ 轮操作，第 $i$ 轮操作给定 $a_i$ 与 $b_i$，jiangly 可以选择交换 $P_{a_i}$ 与 $P_{b_i}$，或者本轮不操作。
• 如果 $m$ 轮操作完后排列 $P$ 严格递增，则游戏胜利，否则失败。

jiangly 认为，将 $P$ 升序排序的最快方法是尽可能减少逆序对个数$^{\ddagger}$。所以他会采取以下策略：

• 对于第 $i$ 轮，如果交换后 $P$ 的逆序对个数减少，则本轮交换；否则不交换。

请你输出 jiangly 的游戏过程，并判断最终是否胜利。

$^{\dagger}$：长度为 $n$ 的排列是指一个包含 $1$ 到 $n$ 中每个正整数各恰好一次的序列。例如，$[2, 3, 1, 5, 4]$ 是一个长度为 $5$ 的排列，而 $[1, 2, 2]$ 和 $[1, 3, 4]$ 则不是。

$^{\ddagger}$：对于一个排列 $P$，若存在一对下标 $(i,j)$ 满足 $1 \le i < j \le n$ 且 $P_i > P_j$，则称 $(i,j)$ 是 $P$ 的一个逆序对。排列 $P$ 中逆序对的总数称为 $P$ 的逆序对个数。

格式

输入格式

第一行包含两个整数 $n,m$，表示排列长度和操作个数。

第二行包含 $n$ 个整数 $P_1,P_2,\cdots,P_n$，表示排列 $P$。保证输入为排列。

第 $3\sim m+2$ 行每行包含两个整数 $a_i,b_i$，第 $i+2$ 行表示第 $i$ 个操作。

输出格式

输出 $m+1$ 行：

第一行包含一个字符串，若最终胜利输出 Win，否则输出 Lose。

第 $2\sim m+1$ 行，每行包含一个字符串 Yes 或 No，第 $i+1$ 行表示第 $i$ 个操作是否交换。

样例

样例输入 #1

3 2
2 1 3
1 2
2 3

样例输出 #1

Win
Yes
No

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n,m\le$
$1$	$40$	$100$
$2$	$20$	$5000$
$3$	$40$	$2 \times 10^5$

对于 $100\%$ 的数据，保证 $1\le n,m\le 2 \times 10^5$，$1\le a_i,b_i\le n$，$a_i\neq b_i$，保证 $P$ 为排列。