CF331B2 Shave Beaver!

聪明的海狸最近设计并制造出了一台创新的纳米技术全能海狸剃毛机——“Beavershave 5000”。Beavershave 5000 可以按家族为单位剃海狸！它是如何工作的呢？非常简单！ 有 $n$ 只海狸，每只海狸都有一个唯一的编号，从 $1$ 到 $n$。考虑一个长度为 $n$ 的排列 $a_1, a_2, ..., a_n$，表示这些海狸的编号。Beavershave 5000 只需要一次操作就能剃掉编号从 $x$ 到 $y$（包含 $x$ 和 $y$）的所有海狸，当且仅当存在一组下标 $i_1 < i_2 < ... < i_k$，使得 $a_{i_1}=x$，$a_{i_2}=x+1$，...，$a_{i_{k-1}}=y-1$，$a_{i_k}=y$。这非常方便。例如，对于排列 $1,2,3,...,n$，只需要一次操作就能剃掉所有海狸。 如果不能在一次操作中剃掉编号从 $x$ 到 $y$ 的所有海狸，那么可以将这些海狸分成若干组 $[x,p_1]$，$[p_1+1,p_2]$，...，$[p_m+1,y]$（$x \leq p_1 < p_2 < ... < p_m < y$），使得机器可以对每组分别进行一次剃毛操作。此时，Beavershave 5000 需要 $m+1$ 次操作才能剃掉编号从 $x$ 到 $y$ 的所有海狸。 所有海狸都很不安分，他们总是试图交换位置。因此，如果更正式地描述这个问题，可以考虑两种类型的操作： - 询问 Beavershave 5000 剃掉编号从 $x$ 到 $y$（包含 $x$ 和 $y$）的所有海狸，所需的最少操作次数是多少？ - 交换位置 $x$ 和 $y$ 上的两只海狸（即交换 $a_x$ 和 $a_y$）。 你可以假设每只海狸可以被剃任意多次。

第一行包含一个整数 $n$，表示海狸的总数，$2 \leq n$。第二行包含 $n$ 个用空格分隔的整数，表示初始的海狸排列。 第三行包含一个整数 $q$，表示操作的数量，$1 \leq q \leq 10^5$。接下来的 $q$ 行，每行描述一个操作。每个操作 $i$ 形如 $p_i\ x_i\ y_i$，其中 $p_i$ 表示操作类型（$1$ 表示询问编号从 $x_i$ 到 $y_i$ 的最少剃毛次数，$2$ 表示交换位置 $x_i$ 和 $y_i$ 上的海狸）。所有操作满足 $1 \leq x_i < y_i \leq n$。 - 若要获得 30 分，需要满足 $n \leq 100$（子任务 B1）； - 若要获得 100 分，需要满足 $n \leq 3 \cdot 10^5$（子任务 B1+B2）。 注意，在子任务 B1 和 B2 中，操作数 $q$ 都满足 $1 \leq q \leq 10^5$。

对于每个 $p_i=1$ 的操作，输出 Beavershave 5000 所需的最少操作次数。

由 ChatGPT 4.1 翻译