问题2703--仓鼠与排序

2703: 仓鼠与排序

时间限制: 2 Sec  内存限制: 32 MB
提交: 5  解决: 3
[状态] [讨论版] [提交] [命题人:]
题目描述

作为仓鼠世界中一位伟大的计算机科学家,小仓鼠非常热衷于发明新算法。最近,他发现了一个用于对排列进行排序的全新算法,他决定以自己主人的名字命名为“WK算法

WK算法可以从一个无序排列中(从1开始)提取任意一个首项为1,公差为k

以下是WK算法的具体流程:

创建一个空数组v,反复从前往后遍历原排列,用v存储已经找到的答案。

记当前遍历到的值为pi,如果它满足以下任一条件,我们就把它插入到v的最后:

(1) pi=1 并且当前数组v是空的。

(2)pi=vlast+k, 这里vlast是上一个被插入数组末端的值。

vlast+k>n时,结束算法。

小仓鼠已经证明出了这个算法的时间复杂度是O(n*T), 是我们遍历整个数组的次数(如果有一次遍历没有遍历完整个数组的话,也记作遍历了一次)

比如说,如果p={4,2,1,3,7,5,6}并且k=1, 那么T就是4。每次找到的元素分别是: {1},{2,3},{4,5,6},{7}.然后如果k=2, T=2,情况就变成了:{1,3,5},{7}.
现在小仓鼠决定考一考你:他会给你一个从n的排列p和一系列询问:每次给定一个k, .需要计算出在此时需要的遍历次数T。为了增大难度, 小仓鼠还会在询问之间时不时地交换两个元素!

输入

第一行会给出一个整数n , 表示排列的长度。n105

接下来的一行当中总共会给出n个以空格分隔的整数,保证这些数构成了一个1n的排列。

第三行会有一个整数m ------表示事件总数。m105

对于接下来的m行,每一行会描述一个事件, 它们的格式为以下两种形式之一:

1XY,这表示小仓鼠在此时交换了排列中的第X个元素和第Y个元素。
2K, 这表示一次询问。你需要找出传入参数K之后运行WK算法时总共需要遍历数组的次数T

输出

对于每一次询问,你需要输出一个整数,表示这个询问的答案

样例输入 Copy
7
4 2 1 3 7 5 6
4
2 1
2 2
1 5 6
2 2
样例输出 Copy
4
2
1