← 返回题目列表

Codeforces · 331/B2

B2. 给海狸剃毛!

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

Smart Beaver 最近设计并制造了一款创新的纳米技术通用海狸剃须机“Beavershave 5000”。 Beavershave 5000 可以家庭给海狸剃毛!它是如何运作的?很容易!

有n只海狸,每只海狸都有一个从1到n的唯一id。考虑 n 个海狸的排列 a1, a2, ..., an。 Beavershave 5000 需要一次会话来为 id 从 x 到 y(含)的海狸剃毛,当且仅当存在这样的索引 i1 < i2 < ... < ik,即 ai1 = x、ai2 = x + 1、...、aik - 1 = y - 1、aik = y。这真的很方便。例如,它需要一个会话来剃除海狸 1、2、3、...、n 的排列。

如果我们不能在一次会话中将 x 到 y 的海狸剃毛,那么我们可以将这些海狸分为 [x, p1], [p1 + 1, p2], ..., [pm + 1, y] (x ≤ p1 < p2 < ... < pm < y) 组,这样机器就可以在一次会话中为每个组中的海狸剃毛。但是 Beavershave 5000 需要 m + 1 个工作会话才能将海狸从 x 剃到 y。

所有海狸都焦躁不安,不断尝试交换。因此,如果我们更正式地考虑这个问题,我们可以考虑两种类型的查询:

- Beavershave 5000 为 ID 从 x 到 y(含)的海狸剃毛所需的最少会话数是多少?
- 位置 x 和 y 上的两只海狸(海狸 ax 和 ay)交换了。

您可以假设任何海狸都可以被剃毛任意次数。

输入

第一行包含整数 n — 海狸的总数,2 ≤ n。第二行包含 n 个空格分隔的整数——初始海狸排列。

第三行包含整数 q — 查询数,1 ≤ q ≤ 105。接下来的 q 行包含查询。每个查询 i 看起来为 pi xi yi,其中 pi 是查询类型(1 是将海狸从 xi 剃到 yi(含),2 是将海狸位置 xi 和 yi 交换)。所有查询都满足条件:1 ≤ xi < yi ≤ n。

- 要获得 30 分,需要解决具有约束条件的问题:n ≤ 100(子问题 B1);
- 要获得 100 分,您需要解决具有约束条件的问题:n ≤ 3·105(子问题 B1+B2)。

请注意,在子问题 B1 和子问题 B2 中,查询 q 的数量都被限制为 1 ≤ q ≤ 105。

输出

对于 pi = 1 的每个查询,打印 Beavershave 5000 会话的最小数量。

示例

输入 #1

5
1 3 4 2 5
6
1 1 5
1 3 4
2 2 3
1 1 5
2 1 5
1 1 5

输出 #1

2
1
3
5