CF1540D Inverse Inversions

你正在玩一个长度为 $n$ 的排列 $p$，但你在 Blair, Alabama 把它弄丢了！ 幸运的是，你还记得关于这个排列的一些信息。更具体地说，你记得一个长度为 $n$ 的数组 $b$，其中 $b_i$ 表示有多少个下标 $j$ 满足 $j < i$ 且 $p_j > p_i$。 你现在有数组 $b$，并且你想找回排列 $p$。然而，你的记忆并不完美，随着你了解得更多，你会不断修改 $b$ 的值。在接下来的 $q$ 秒内，会发生以下两种情况之一： 1. $1\ i\ x$ —— 你意识到 $b_i$ 等于 $x$； 2. $2\ i$ —— 你需要找出 $p_i$ 的值。如果有多个答案，输出任意一个即可。在本题的约束下，总是存在至少一个可能的答案。 请回答所有的查询，帮助你记起这个数组！

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示排列的大小。 第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$0 \leq b_i < i$），表示你最初记忆中的数组 $b$。 第三行包含一个整数 $q$（$1 \leq q \leq 10^5$），表示查询的数量。 接下来的 $q$ 行，每行包含以下两种格式之一： - $1\ i\ x$（$0 \leq x < i \leq n$），表示类型 $1$ 的查询。 - $2\ i$（$1 \leq i \leq n$），表示类型 $2$ 的查询。 保证至少有一个类型 $2$ 的查询。

对于每个类型 $2$ 的查询，输出一个整数，表示该查询的答案。

对于第一个样例，最初只有一个满足条件的排列 $[1, 2, 3]$，因为它必须没有逆序对。 经过类型 $1$ 的查询后，数组 $b$ 变为 $[0, 1, 0]$。唯一能产生该数组的排列是 $[2, 1, 3]$。在这个排列中，$b_2$ 等于 $1$，因为 $p_1 > p_2$。 由 ChatGPT 4.1 翻译