题解：区间排序

题目分析

给定一个长度为 $n$ 的正整数序列，需要对其进行 $q$ 次操作。每次操作指定一个区间 $[l, r]$，要求将该区间内的元素按升序排序，并且后续操作都在前一次操作的结果上进行。最终输出经过所有操作后的序列。

由于数据规模很小（$n, q \le 100$），我们完全可以使用最直接的方法——每次操作时对指定区间进行排序。

解题思路

核心思路是模拟。维护一个全局数组 a，每读入一个操作区间，就对数组的对应部分进行升序排序。由于题目没有特殊要求，选择任何一种稳定的排序方法都可以。最简便的方法是直接使用 C++ 标准库中的 sort 函数，当然也可以自己实现冒泡排序、选择排序等。

本题参考代码中使用了对指定区间执行冒泡排序的方法，思路清晰，非常适合初学者理解排序过程。

算法说明

冒泡排序

冒泡排序的基本思想是：反复遍历要排序的区间，每次比较相邻的两个元素，如果前面的比后面的大就交换它们。这样每一轮遍历都会把当前未排序部分的最大值“浮”到区间的末尾。重复这个过程，直到整个区间有序。

参考代码中对区间 [l, r] 进行排序的冒泡排序实现如下：

cpp
复制
1void bubbleSort(int l, int r) {
2    bool flag = true;
3    while (flag) {               // 如果还有交换发生，继续循环
4        flag = false;
5        for (int i = l; i < r; ++i) {
6            if (a[i] > a[i + 1]) {
7                flag = true;
8                swap(a[i], a[i + 1]);
9            }
10        }
11    }
12}

在 main 函数中，每次读入 $l$ 和 $r$ 后直接调用该函数即可。

时间复杂度分析

每次操作需要对长度为 $len = r - l + 1$ 的区间进行排序。冒泡排序的时间复杂度为 $O(len^2)$，最坏情况下 $len = n$，单次排序复杂度为 $O(n^2)$。总共进行 $q$ 次操作，所以整体时间复杂度为 $O(q \cdot n^2)$。

由于本题数据范围 $n, q \le 100$，最坏情况下约 $100 \times 10000 = 10^6$ 次操作，完全可以在 1 秒内运行完成。

空间复杂度：仅需一个长度为 $n$ 的数组，额外空间复杂度 $O(n)$。

参考代码

以下是完整的参考代码，并对关键部分进行注释解释。

cpp
复制
1#include<bits/stdc++.h>
2using namespace std;
3
4const int N = 1010;
5int a[N];       // 存储序列，1 为起始下标
6int n;
7
8// 对数组 a 的区间 [l, r] 进行冒泡排序
9void bubbleSort(int l, int r) {
10    bool flag = true;               // 标记本轮是否有交换
11    while (flag) {                  // 有交换则继续循环
12        flag = false;
13        for (int i = l; i < r; ++i) {
14            if (a[i] > a[i + 1]) {  // 如果前面的数大于后面的数
15                flag = true;        // 标记发生了交换
16                swap(a[i], a[i + 1]);
17            }
18        }
19    }
20}
21
22int main() {
23    // 读入序列长度和元素
24    cin >> n;
25    for (int i = 1; i <= n; i++) {
26        cin >> a[i];
27    }
28
29    // 读入操作次数并依次处理
30    int q;
31    cin >> q;
32    while (q--) {
33        int l, r;
34        cin >> l >> r;
35        bubbleSort(l, r);          // 对指定区间排序
36    }
37
38    // 输出最终序列
39    for (int i = 1; i <= n; i++) {
40        cout << a[i];
41        if (i != n)
42            cout << " ";
43        else
44            cout << "\n";
45    }
46    return 0;
47}

代码说明

1. 数组下标从 1 开始：这样更符合题目中区间 $[l, r]$ 的含义，也方便理解。
2. 冒泡排序函数：传入区间端点，通过一个 while 循环反复扫描区间，每扫一次如果没有任何交换发生，说明区间已经有序，直接结束。
3. 主函数流程：
   • 输入 $n$ 和初始序列；
   • 输入 $q$，循环执行 $q$ 次排序；
   • 每次读入 $l, r$ 后调用 bubbleSort 对数组直接修改；
   • 所有操作完成后按格式输出最终序列。

拓展思考

虽然本题数据很小，用冒泡排序足以通过，但同学们也可以尝试使用 sort(a + l, a + r + 1) 来简化代码。在更大的数据范围下，冒泡排序会超时，此时就应当使用标准库中更高效的排序算法。

---

希望这篇题解能帮助大家理解区间排序的模拟过程，顺利通过此题。