A186075.书架清点
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
书架上从左到右摆放着 n 本书,每本书都有一个不同的编号,所有编号恰好为 1∼n。
管理员需要按照编号 1,2,…,n 的顺序登记这些书。每轮清点时,他从书架最左端开始,向右依次检查每个位置:
- 如果当前位置的书恰好是下一本需要登记的书,就登记它,并将待登记编号增加 1;
- 否则跳过当前位置,继续向右;
- 扫描到最右端后,如果还有书未登记,就从最左端开始新的一轮。
登记不会移动或取走书籍。全部书登记完毕的那一轮也计入总轮数。
现在需要进行 q 次交换。每次给出两个位置 u,v,交换这两个位置上的书;若 u=v,排列保持不变。
每次交换后,请你计算:如果从编号 1 开始重新登记全部书籍,需要多少轮清点。
交换依次进行,后一次交换以之前交换后的排列为基础;每次计算清点轮数时,登记进度都重新开始。
输入格式
第一行输入两个整数 n,q,分别表示书籍数量和交换次数。
第二行输入 n 个整数 a1,a2,…,an,其中 ai 表示最初位于第 i 个位置的书的编号。
接下来 q 行,每行输入两个整数 u,v,表示需要交换的两个位置。位置从左到右编号为 1∼n。
输出格式
输出 q 行,每行一个整数,表示对应交换完成后,重新登记全部书籍需要的清点轮数。
输入输出样例
输入#1
5 3 4 2 1 5 3 1 3 1 5 3 3
输出#1
2 3 3
输入#2
1 2 1 1 1 1 1
输出#2
1 1
说明/提示
样例解释 1
第一次交换后的排列为 1,2,4,5,3。第一轮登记 1,2,3,第二轮登记 4,5,共 2 轮。
第二次交换后的排列为 3,2,4,5,1。三轮分别登记 1、2、3,4,5,共 3 轮。
第三次交换的位置相同,排列不变,因此仍需 3 轮。
样例解释 2
只有一本书,每次交换后仍然只需一轮。
数据范围
对于所有测试数据,保证:
- 1≤n,q≤2×105;
- a1,a2,…,an 是 1∼n 的一个排列;
- 每次交换均满足 1≤u,v≤n,允许 u=v。
输入解题思路,AI测评打分。不知道怎么写?