A186075.书架清点

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

书架上从左到右摆放着 nn 本书,每本书都有一个不同的编号,所有编号恰好为 1∼n1\sim n。

管理员需要按照编号 1,2,…,n1,2,\ldots,n 的顺序登记这些书。每轮清点时,他从书架最左端开始,向右依次检查每个位置:

  • 如果当前位置的书恰好是下一本需要登记的书,就登记它,并将待登记编号增加 11;
  • 否则跳过当前位置,继续向右;
  • 扫描到最右端后,如果还有书未登记,就从最左端开始新的一轮。

登记不会移动或取走书籍。全部书登记完毕的那一轮也计入总轮数。

现在需要进行 qq 次交换。每次给出两个位置 u,vu,v,交换这两个位置上的书;若 u=vu=v,排列保持不变。

每次交换后,请你计算:如果从编号 11 开始重新登记全部书籍,需要多少轮清点。

交换依次进行,后一次交换以之前交换后的排列为基础;每次计算清点轮数时,登记进度都重新开始。

输入格式

第一行输入两个整数 n,qn,q,分别表示书籍数量和交换次数。

第二行输入 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,其中 aia_i 表示最初位于第 ii 个位置的书的编号。

接下来 qq 行,每行输入两个整数 u,vu,v,表示需要交换的两个位置。位置从左到右编号为 1∼n1\sim n。

输出格式

输出 qq 行,每行一个整数,表示对应交换完成后,重新登记全部书籍需要的清点轮数。

输入输出样例

  • 输入#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,31,2,4,5,3。第一轮登记 1,2,31,2,3,第二轮登记 4,54,5,共 22 轮。

第二次交换后的排列为 3,2,4,5,13,2,4,5,1。三轮分别登记 11、22、3,4,53,4,5,共 33 轮。

第三次交换的位置相同,排列不变,因此仍需 33 轮。

样例解释 2

只有一本书,每次交换后仍然只需一轮。

数据范围

对于所有测试数据,保证:

  • 1≤n,q≤2×1051\le n,q\le2\times10^5;
  • a1,a2,…,ana_1,a_2,\ldots,a_n 是 1∼n1\sim n 的一个排列;
  • 每次交换均满足 1≤u,v≤n1\le u,v\le n,允许 u=vu=v。

输入解题思路,AI测评打分。不知道怎么写?

首页