CF2147F.Exchange Queries

You are at a marketplace and there are two traders who are willing to trade on $n$ different items. Each trader is represented by a permutation that signifies the relative value of the $n$ items for that trader. Let's denote those two permutations $p$ and $s$. If you have an item $i$, you can trade it for an item $j$ if either $p_i \gt p_j$ (using the first trader) or $s_i \gt s_j$ (using the second trader).

We say that an item $i$ is at least as valuable as an item $j$ if you can come to the marketplace with item $i$, make some (possibly none) trades, and get item $j$. Note that at any moment, you will have exactly one item on hand. Assume that the traders have infinite supplies of any item.

Due to the never-ending updates in the market, traders will often reevaluate their views on the item values. You will be given $q$ queries; each is a swap in one of the permutations. After every update, you should print the number of pairs $(i, j)$ ($1 \le i, j \le n$) such that item $i$ is at least as valuable as item $j$.

你身处一个市场，这里有两位交易者愿意就 $n$ 种不同物品进行交易。每位交易者由一个排列表示，该排列刻画了该交易者对这 $n$ 种物品的相对价值评估。我们记这两个排列为 $p$ 和 $s$。若你持有物品 $i$，则当且仅当 $p_i > p_j$（使用第一位交易者）或 $s_i > s_j$（使用第二位交易者）时，你可以将物品 $i$ 交易为物品 $j$。

我们称物品 $i$ 至少与物品 $j$ 一样有价值，当且仅当你带着物品 $i$ 进入市场，经过若干次（可能为零次）交易后，最终获得物品 $j$。注意：在任意时刻，你手中恰好持有一件物品。假设两位交易者对任意物品均有无限供应。

由于市场持续更新，交易者会频繁重新评估他们对物品价值的看法。你将收到 $q$ 个查询；每个查询表示对其中一个排列执行一次交换操作。每次更新后，你需要输出满足“物品 $i$ 至少与物品 $j$ 一样有价值”的有序对 $(i, j)$（其中 $1 \le i, j \le n$）的总数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($2 \le n \le 10^5$, $1 \le q \le 10^5$).

The next two lines contain the initial permutations $p$ and $s$.

The following $q$ lines each contain three integers $tp$, $i$, $j$ ($tp \in { 1, 2 }$, $1 \le i, j \le n$, $i \ne j$). If $tp=1$, swap $p_i$ with $p_j$. If $tp=2$, swap $s_i$ with $s_j$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$, and the sum of $q$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 10^5$，$1 \le q \le 10^5$）。

接下来两行分别给出初始排列 $p$ 和 $s$。

随后的 $q$ 行中，每行包含三个整数 $tp$、$i$、$j$（$tp \in \{ 1, 2 \}$，$1 \le i, j \le n$，$i \ne j$）。若 $tp = 1$，则交换 $p_i$ 与 $p_j$；若 $tp = 2$，则交换 $s_i$ 与 $s_j$。

保证所有测试用例的 $n$ 之和不超过 $10^5$，且所有测试用例的 $q$ 之和不超过 $10^5$。

For each test case, output $q$ lines, the $k$-th of them containing a single integer — the number of pairs $(i, j)$ such that item $i$ is at least as valuable as item $j$ after the first $k$ updates.

对于每个测试用例，输出 $q$ 行，其中第 $k$ 行包含一个整数——表示在前 $k$ 次更新之后，满足物品 $i$ 的价值至少与物品 $j$ 相当的二元组 $(i, j)$ 的数量。

In the first test case, after the first update, both permutations are the identity permutations and thus the only valid pairs are $(1, 1)$, $(2, 1)$, $(2, 2)$, $(3, 1)$, $(3, 2)$, and $(3, 3)$. After the second update, it is possible to get any item starting with any item. For instance, you can get item $3$ from item $1$ using the second trader since $s_1 = 3 \gt 1 = s_3$. After the third update, it is still possible to get any item starting with any item. For instance, if you start with item $2$ and want to get item $1$, you can first exchange your item $2$ for item $3$ using the second trader, and then exchange item $3$ for item $1$ using the first trader.

在第一个测试用例中，第一次更新后，两个排列均为单位排列，因此唯一有效的数对为 $(1, 1)$、$(2, 1)$、$(2, 2)$、$(3, 1)$、$(3, 2)$ 和 $(3, 3)$。第二次更新后，可以从任意物品出发获得任意其他物品。例如，你可以利用第二位交易者从物品 $1$ 获得物品 $3$，因为 $s_1 = 3 \gt 1 = s_3$。第三次更新后，仍然可以从任意物品出发获得任意其他物品。例如，若你起始持有物品 $2$ 并希望获得物品 $1$，可先利用第二位交易者将物品 $2$ 换成物品 $3$，再利用第一位交易者将物品 $3$ 换成物品 $1$。