CF1638C Inversion Graph

给定一个排列 $p_1, p_2, \dots, p_n$。然后，按照如下方式构建一个无向图：对于所有满足 $i < j$ 且 $p_i > p_j$ 的点对 $(i, j)$，在顶点 $i$ 和 $j$ 之间添加一条边。你的任务是计算该图中连通块的数量。 如果存在一条由边连接的路径能够从顶点 $u$ 到达顶点 $v$，则称顶点 $u$ 和 $v$ 属于同一个连通块。 排列是一个长度为 $n$ 的数组，包含 $1$ 到 $n$ 的所有不同整数，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中有 $4$）。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示排列的长度。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$），表示排列的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数 $k$，表示连通块的数量。

下图展示了每个独立测试用例的情况。彩色方块表示排列的元素，对于一个排列，每种颜色代表一个连通块。不同颜色的数量即为答案。  由 ChatGPT 4.1 翻译