#B4171. [BCSP-X 2024 6 月小学高年级组] 选择排序

[BCSP-X 2024 6 月小学高年级组] 选择排序

题目描述

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每趟找出第 ii 小的元素(也就是 A[in]A[i \sim n] 中最小的元素),然后将这个元素与数组第 ii 个位置上的元素 A[i]A[i] 交换;在 n1n-1 趟之后序列 AA 变为升序。

例如 A=[3,4,1,5,2]A = [3, 4, 1, 5, 2]

  • 第 1 趟交换 A[1],A[3]A[1], A[3],序列变为 [1,4,3,5,2][1, 4, 3, 5, 2]
  • 第 2 趟交换 A[2],A[5]A[2], A[5],序列变为 [1,2,3,5,4][1, 2, 3, 5, 4]
  • 第 3 趟交换 A[3],A[3]A[3], A[3],序列不变;
  • 第 4 趟交换 A[4],A[5]A[4], A[5],序列变为 [1,2,3,4,5][1, 2, 3, 4, 5]

现在给定初始序列 A[1n]A[1 \sim n](保证 AA 是排列,即 1n1 \sim n 每个数恰好出现一次)和 mm 个询问 q[1,2,,m]q[1, 2, \ldots, m](保证 q[i]<q[i+1]q[i] < q[i + 1]),请你依次输出第 q[i]q[i] 趟之后的序列 AA

输入格式

第一行 2 个整数 n,mn, m

第二行 nn 个整数 A[1n]A[1 \sim n],保证 AA 是排列。

第三行 mm 个整数 q[1m]q[1 \sim m],保证 q[i]<q[i+1]q[i] < q[i + 1]

输出格式

输出 mm 行,第 ii 行包含 nn 个整数代表第 q[i]q[i] 趟之后的序列 AA

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

提示

对于所有数据,满足 $1 \leq n \leq 10^5, 1 \leq m \leq 10, 1 \leq A[i] \leq n, 1 \leq q[i] < q[i + 1] < n$,保证 AA 是排列。

  • 对于测试点 1~8:n10n \leq 10
  • 对于测试点 9~13:n2000n \leq 2000
  • 对于测试点 14~20:n105n \leq 10^5