CF2147F Exchange Queries

你现在在一个市场上，有两个交易者愿意就 $n$ 种不同的物品进行交易。每个交易者由一个排列表示，表示对于该交易者来说这 $n$ 个物品的相对价值。我们用这两个排列 $p$ 和 $s$ 来表示。如果你拥有物品 $i$，你可以将它与物品 $j$ 交换，如果 $p_i > p_j$（通过第一个交易者）或者 $s_i > s_j$（通过第二个交易者）。 我们称物品 $i$ 至少和物品 $j$ 一样有价值，如果你可以带着物品 $i$ 来到市场，经过若干次（也可以为零次）交换，最终得到物品 $j$。注意，在任意时刻，你手上始终只有一个物品，并且交易者可以无限次提供任意物品。 由于市场在不断变化，交易者也会频繁地重新评价物品的价值。你将会得到 $q$ 次操作，每次是某个排列上的一次交换。每次操作后，你需要输出所有满足物品 $i$ 至少和物品 $j$ 一样有价值的有序对 $(i, j)$ 共多少对。

每组测试数据包含多组测试用例。第一行输入测试用例数量 $t$（$1 \leq t \leq 10^4$）。 每组测试用例的第一行输入两个整数 $n$ 和 $q$（$2 \leq n \leq 10^5$，$1 \leq q \leq 10^5$）。 接下来的两行，每行分别输入初始排列 $p$ 和 $s$。 接下来 $q$ 行，每行输入三个整数 $tp$、$i$、$j$（$tp \in \{1, 2\}$，$1 \leq i, j \leq n$，$i \neq j$）。 若 $tp=1$，则交换 $p_i$ 与 $p_j$； 若 $tp=2$，则交换 $s_i$ 与 $s_j$。 保证所有测试用例的 $n$ 之和不超过 $10^5$，$q$ 之和不超过 $10^5$。

对于每个测试用例，输出 $q$ 行，第 $k$ 行输出经过第 $k$ 次操作后，满足物品 $i$ 至少和物品 $j$ 一样有价值的有序对 $(i, j)$ 的数量。

在第一个测试用例中，第一次操作后，两组排列都是本原排列，因而只有如下 $(i, j)$ 对是合法的：$(1, 1)$，$(2, 1)$，$(2, 2)$，$(3, 1)$，$(3, 2)$，$(3, 3)$。第二次操作后，从任意物品都可以通过若干次交易得到任意其他物品，例如你可以从物品 $1$ 通过第二个交易者换到物品 $3$，因为 $s_1=3 > 1=s_3$。第三次操作后仍然可以从任意物品得到任意其他物品，比如，从物品 $2$ 出发想要获得物品 $1$，可以先通过第二个交易者将物品 $2$ 换为 $3$，再通过第一个交易者将 $3$ 换为 $1$。 由 ChatGPT 5 翻译