← 返回题目列表

Codeforces · 1540/D

D. 逆向反转

中文机器翻译题面 查看原题

你正在玩长度 $$$n$$$ 的排列 $$$p$$$,但你在阿拉巴马州布莱尔输了!

幸运的是,您还记得一些有关排列的信息。更具体地说,您记得一个长度为 $$$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

3
0 0 0
7
2 1
2 2
2 3
1 2 1
2 1
2 2
2 3

输出 #1

1
2
3
2
1
3

输入 #2

5
0 1 2 3 4
15
2 1
2 2
1 2 1
2 2
2 3
2 5
1 3 0
1 4 0
2 3
2 4
2 5
1 4 1
2 3
2 4
2 5

输出 #2

5
4
4
3
1
4
5
1
5
4
1

注意

对于第一个样本,最初只有一个可能的排列满足约束:$$$[1, 2, 3]$$$,因为它必须有 $$$0$$$ 反转。

查询$$$1$$$类型后,数组$$$b$$$为$$$[0, 1, 0]$$$。生成此数组的唯一排列 $$$p$$$ 是 $$$[2, 1, 3]$$$。通过这种排列,$$$b_2$$$ 等于 $$$1$$$,因为 $$$p_1 > p_2$$$。