交换元素列表排序列表切片P0177

按区间整理仓库货架

仓库货架的一排放着 n 个箱子，格子编号从左到右为 1, 2, …, n。
第二行按格子顺序给出 n 个箱子的重量。
第三行给出命令数 q，接下来 q 行每行一个命令。
命令有三种。
"swap i j" 交换 i 号格和 j 号格的箱子（i 和 j 相同时不变，i 也可能大于 j）。
"sort l r" 只把 l 号格到 r 号格（含两端）的箱子按轻的在左排好。
这个区间以外的箱子不动。
"show l r" 在一行中输出当前 l 号格到 r 号格（含两端）的重量，用一个空格隔开。
每个 show 命令输出一行，按命令顺序输出。

输入: 1 ≤ n ≤ 1000，1 ≤ q ≤ 1000，1 ≤ 重量 ≤ 1,000,000（整数）。
swap 满足 1 ≤ i, j ≤ n，sort、show 满足 1 ≤ l ≤ r ≤ n。
至少有一个 show 命令，所有 show 输出的重量合计不超过 20,000 个
输出: 每个 show 命令一行

样例 1 · stdin

6
30 4 100 25 9 7
5
sort 2 5
show 1 6
swap 1 6
sort 4 6
show 3 5

stdout

30 4 9 25 100 7
9 25 30

样例 2 · stdin

3
5 1 3
4
show 2 2
swap 3 3
sort 1 1
show 1 3

stdout

1
5 1 3

main.py 编程语言运行版本

输入(stdin)

运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。

$ 就绪

请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。

其他语言怎么写？查看各语言题解 · 8 种语言题解

截取并排序列表的一个区间，各语言在“含不含终点”“是副本还是原地”上有分歧。
截取从 1 数起的 l ～ r（含两端）：Python a[l-1:r]，JS/TS a.slice(l-1, r)，Java Arrays.copyOfRange(a, l-1, r)（三者都不含终点下标），C# 范围 a[(l-1)..r]（同样不含终点），Craykon a.子列表(l-1, r-l+1)（韩文 부분목록，起点和个数）。
区间排序：Java Arrays.sort(a, l-1, r) 和 C++ std::sort(a.begin()+l-1, a.begin()+r) 不含终点、原地排序，C# Array.Sort(a, l-1, r-l+1) 和 C qsort(a+l-1, r-l+1, …) 接收起点和个数。
陷阱一：Python a[l-1:r].sort() 排序的是截出来的副本，排完就扔掉了，货架不变。
要写成 a[l-1:r] = sorted(a[l-1:r]) 放回去。
Craykon 的 子列表 也是新列表，排序后要逐格写回，JS 用 splice 放回。
陷阱二：JS/TS 的 sort() 不给比较函数时会把数转成字符串比较，[10, 9, 100] 会变成 [10, 100, 9]。
要用 sort((u, v) => u - v)。
陷阱三：像 C# Array.Sort(a, 起点, 终点) 那样把终点下标当第三个参数，个数就错了，会排到区间外或报错。
陷阱四：像 a[l-1:r-1] 那样少截一个，就漏掉 r 号格。
交换两个格子：Python a[i], a[j] = a[j], a[i]，JS/TS 解构赋值，C# 元组，C++ std::swap，Java、C、Craykon 用临时变量。

Pythonmain.py · 18 行

import sys lines = sys.stdin.read().split("\n")n = int(lines[0])shelf = list(map(int, lines[1].split()))q = int(lines[2])out = []for line in lines[3:3 + q]:    cmd, a, b = line.split()    a, b = int(a) - 1, int(b)          # 0부터 세는 시작 a, 끝 b(b는 들어가지 않음)    if cmd == "swap":        i, j = a, b - 1        shelf[i], shelf[j] = shelf[j], shelf[i]    elif cmd == "sort":        shelf[a:b] = sorted(shelf[a:b])  # 잘라 낸 것은 사본이라 정렬한 뒤 그 자리에 다시 넣는다    else:        out.append(" ".join(map(str, shelf[a:b])))print("\n".join(out))

JavaScriptmain.js · 19 行

const lines = require("fs").readFileSync(0, "utf8").split("\n");const shelf = lines[1].trim().split(/\s+/).map(Number);const q = Number(lines[2]);const out = [];for (const line of lines.slice(3, 3 + q)) {  const [cmd, x, y] = line.trim().split(" ");  const a = Number(x) - 1;  const b = Number(y); // slice(a, b)는 b를 넣지 않는다  if (cmd === "swap") {    [shelf[a], shelf[b - 1]] = [shelf[b - 1], shelf[a]];  } else if (cmd === "sort") {    // 비교 함수가 없으면 문자열로 비교해서 "10" < "9"가 된다    const part = shelf.slice(a, b).sort((u, v) => u - v);    shelf.splice(a, part.length, ...part);  } else {    out.push(shelf.slice(a, b).join(" "));  }}console.log(out.join("\n"));

TypeScriptmain.ts · 20 行

import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const shelf: number[] = lines[1].trim().split(/\s+/).map(Number);const q = Number(lines[2]);const out: string[] = [];for (const line of lines.slice(3, 3 + q)) {  const [cmd, x, y] = line.trim().split(" ");  const a = Number(x) - 1;  const b = Number(y); // slice(a, b)는 b를 넣지 않는다  if (cmd === "swap") {    [shelf[a], shelf[b - 1]] = [shelf[b - 1], shelf[a]];  } else if (cmd === "sort") {    // 비교 함수가 없으면 문자열로 비교해서 "10" < "9"가 된다    const part: number[] = shelf.slice(a, b).sort((u, v) => u - v);    shelf.splice(a, part.length, ...part);  } else {    out.push(shelf.slice(a, b).join(" "));  }}console.log(out.join("\n"));

JavaMain.java · 29 行

import java.io.*;import java.util.*; public class Main {    public static void main(String[] args) throws IOException {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int n = Integer.parseInt(br.readLine().trim());        int[] shelf = Arrays.stream(br.readLine().trim().split(" ")).mapToInt(Integer::parseInt).toArray();        int q = Integer.parseInt(br.readLine().trim());        StringBuilder out = new StringBuilder();        for (int k = 0; k < q; k++) {            String[] p = br.readLine().trim().split(" ");            int a = Integer.parseInt(p[1]) - 1;            int b = Integer.parseInt(p[2]); // 끝 자리 b는 들어가지 않는다(toIndex)            if (p[0].equals("swap")) {                int tmp = shelf[a];                shelf[a] = shelf[b - 1];                shelf[b - 1] = tmp;            } else if (p[0].equals("sort")) {                Arrays.sort(shelf, a, b); // 그 구간만 제자리에서 정렬            } else {                StringJoiner sj = new StringJoiner(" ");                for (int w : Arrays.copyOfRange(shelf, a, b)) sj.add(String.valueOf(w));                out.append(sj).append('\n');            }        }        System.out.print(out);    }}

C#Main.cs · 32 行

using System;using System.Linq;using System.Text; class Program{    static void Main()    {        Console.ReadLine();        int[] shelf = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();        int q = int.Parse(Console.ReadLine().Trim());        var sb = new StringBuilder();        for (int k = 0; k < q; k++)        {            string[] p = Console.ReadLine().Trim().Split(' ');            int a = int.Parse(p[1]) - 1, b = int.Parse(p[2]) - 1; // 둘 다 0부터, b도 들어간다            if (p[0] == "swap")            {                (shelf[a], shelf[b]) = (shelf[b], shelf[a]);            }            else if (p[0] == "sort")            {                Array.Sort(shelf, a, b - a + 1); // (시작, 개수)다. 끝 자리가 아니다            }            else            {                sb.Append(string.Join(" ", shelf[a..(b + 1)])).Append('\n'); // 범위 a..c 는 c를 넣지 않는다            }        }        Console.Write(sb);    }}

C++main.cpp · 29 行

#include <algorithm>#include <iostream>#include <string>#include <utility>#include <vector> int main() {    std::ios::sync_with_stdio(false);    int n, q;    std::cin >> n;    std::vector<int> shelf(n);    for (int& w : shelf) std::cin >> w;    std::cin >> q;    std::string out;    for (int k = 0; k < q; k++) {        std::string cmd;        int a, b;        std::cin >> cmd >> a >> b;        if (cmd == "swap") {            std::swap(shelf[a - 1], shelf[b - 1]);        } else if (cmd == "sort") {            std::sort(shelf.begin() + (a - 1), shelf.begin() + b); // [첫, 끝) — 끝은 들어가지 않는다        } else {            for (int i = a - 1; i < b; i++) out += (i > a - 1 ? " " : "") + std::to_string(shelf[i]);            out += "\n";        }    }    std::cout << out;}

Cmain.c · 32 行

#include <stdio.h>#include <stdlib.h> static int ascending(const void* x, const void* y) {    int a = *(const int*)x, b = *(const int*)y;    return (a > b) - (a < b);} int main(void) {    static int shelf[1000];    int n, q;    scanf("%d", &n);    for (int i = 0; i < n; i++) scanf("%d", &shelf[i]);    scanf("%d", &q);    for (int k = 0; k < q; k++) {        char cmd[8];        int a, b;        scanf("%7s %d %d", cmd, &a, &b);        a--, b--; /* 둘 다 0부터 */        if (cmd[1] == 'w') { /* swap */            int tmp = shelf[a];            shelf[a] = shelf[b];            shelf[b] = tmp;        } else if (cmd[1] == 'o') { /* sort: a번부터 (b - a + 1)칸 */            qsort(shelf + a, b - a + 1, sizeof shelf[0], ascending);        } else { /* show */            for (int i = a; i <= b; i++) printf(i > a ? " %d" : "%d", shelf[i]);            printf("\n");        }    }    return 0;}

Craykonmain.cray · 29 行

n = 控制台.读行().转数字();shelf = 控制台.读数字();q = 控制台.读行().转数字();循环 (k = 0; k < q; k++){    p = 控制台.读行().去空白().分割();    a = p[1].转数字() - 1;    b = p[2].转数字() - 1; // 둘 다 0부터, b도 들어간다    如果 (p[0] == "swap")    {        tmp = shelf[a];        shelf[a] = shelf[b];        shelf[b] = tmp;    }    否则 如果 (p[0] == "sort")    {        // 부분목록은 (시작, 개수)로 잘라 낸 새 목록이라, 정렬한 뒤 제자리에 다시 써 넣는다        part = shelf.子列表(a, b - a + 1);        part.排序();        循环 (i = 0; i < part.数量; i++)        {            shelf[a + i] = part[i];        }    }    否则    {        控制台.输出(shelf.子列表(a, b - a + 1).连接(" "));    }}