A16624 · 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)$ 的数量。

输入 #1

输出 #1