{"problem":{"name":"[BCSP-X 2024 6 月小学高年级组] 选择排序","description":{"content":"选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每趟找出第 $i$ 小的元素（也就是 $A[i \\sim n]$ 中最小的元素），然后将这个元素与数组第 $i$ 个位置上的元素 $A[i]$ 交换；在 $n-1$ 趟之后序列 $A$ 变为升序。 例如 $A = [3, 4, 1, 5, 2]$： - 第 1 趟交换 $A[1], A[3]$，序列变为 $[1, 4","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4171"},"statements":[{"statement_type":"Markdown","content":"选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每趟找出第 $i$ 小的元素（也就是 $A[i \\sim n]$ 中最小的元素），然后将这个元素与数组第 $i$ 个位置上的元素 $A[i]$ 交换；在 $n-1$ 趟之后序列 $A$ 变为升序。\n\n例如 $A = [3, 4, 1, 5, 2]$：\n- 第 1 趟交换 $A[1], A[3]$，序列变为 $[1, 4, 3, 5, 2]$；\n- 第 2 趟交换 $A[2], A[5]$，序列变为 $[1, 2, 3, 5, 4]$；\n- 第 3 趟交换 $A[3], A[3]$，序列不变；\n- 第 4 趟交换 $A[4], A[5]$，序列变为 $[1, 2, 3, 4, 5]$；\n\n现在给定初始序列 $A[1 \\sim n]$（保证 $A$ 是排列，即 $1 \\sim n$ 每个数恰好出现一次）和 $m$ 个询问 $q[1, 2, \\ldots, m]$（保证 $q[i] < q[i + 1]$），请你依次输出第 $q[i]$ 趟之后的序列 $A$。\n\n## Input\n\n第一行 2 个整数 $n, m$。\n\n第二行 $n$ 个整数 $A[1 \\sim n]$，保证 $A$ 是排列。\n\n第三行 $m$ 个整数 $q[1 \\sim m]$，保证 $q[i] < q[i + 1]$。\n\n## Output\n\n输出 $m$ 行，第 $i$ 行包含 $n$ 个整数代表第 $q[i]$ 趟之后的序列 $A$。\n\n[samples]\n\n## Note\n\n对于所有数据，满足 $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$，保证 $A$ 是排列。\n\n- 对于测试点 1~8：$n \\leq 10$；\n- 对于测试点 9~13：$n \\leq 2000$；\n- 对于测试点 14~20：$n \\leq 10^5$；","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4171","tags":["2024","北京","排序","BCSP-X"],"sample_group":[["5 4\n3 4 1 5 2\n1 2 3 4","1 4 3 5 2\n1 2 3 5 4\n1 2 3 5 4\n1 2 3 4 5"],["6 3\n6 4 2 3 1 5\n1 3 5","1 4 2 3 6 5\n1 2 3 4 6 5\n1 2 3 4 5 6"]],"created_at":"2026-03-03 11:09:25"}}