G4012 [GESP202409 四级] 区间排序 题解

知识点：排序、数组模拟、区间处理。

解题思路

依次读取闭区间[l,r]，对数组对应范围执行升序排序，全部操作后输出数组。

为什么正确

每轮只改变题面指定的区间，按原顺序模拟全部操作得到最终状态。

易错点

C++排序右端开区间，应使用begin()+r而不是r-1。

复杂度

时间O(Σ Lq log Lq)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q,l,r;
    cin>>n;
    vector<int>a(n);
    for(int &x:a)cin>>x;
    cin>>q;
    while(q--) {
        cin>>l>>r;
        sort(a.begin()+l-1,a.begin()+r);
    }
    for(int x:a)cout<<x<<" ";
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。