Bài 16.4: Thuật toán quicksort trong C++

Chào mừng quay trở lại với series blog về C++! Hôm nay, chúng ta sẽ cùng nhau "mổ xẻ" một trong những thuật toán sắp xếp kinh điển và mạnh mẽ nhất: Quicksort. Nếu bạn đã từng tìm hiểu về sắp xếp, chắc chắn bạn đã nghe qua cái tên này. Quicksort nổi tiếng vì hiệu suất thường thấy rất cao trong thực tế, mặc dù trong trường hợp xấu nhất lại có thể không "quick" như tên gọi của nó.

Vậy, Quicksort hoạt động như thế nào? Tại sao nó lại phổ biến đến vậy? Và làm thế nào để triển khai nó trong C++? Hãy cùng tìm hiểu nhé!

Quicksort là gì? Nguyên lý Hoạt động

Quicksort là một thuật toán sắp xếp dựa trên nguyên tắc "Chia để trị" (Divide and Conquer). Nguyên tắc này bao gồm ba bước chính:

Chia (Divide): Chia bài toán lớn thành các bài toán con nhỏ hơn.
Trị (Conquer): Giải quyết các bài toán con một cách đệ quy.
Kết hợp (Combine): Kết hợp kết quả của các bài toán con để có lời giải cho bài toán lớn.

Đối với Quicksort, các bước này được cụ thể hóa như sau:

Chọn Chốt (Pick a Pivot): Chọn một phần tử từ mảng cần sắp xếp. Phần tử này được gọi là chốt (pivot). Việc chọn chốt ảnh hưởng lớn đến hiệu suất của thuật toán.
Phân hoạch (Partition): Sắp xếp lại mảng sao cho tất cả các phần tử nhỏ hơn chốt nằm về phía bên trái của chốt, và tất cả các phần tử lớn hơn chốt nằm về phía bên phải của chốt. Các phần tử bằng chốt có thể nằm ở bất kỳ bên nào (hoặc tập trung xung quanh chốt). Sau bước này, chốt sẽ nằm ở vị trí cuối cùng của nó trong mảng đã sắp xếp. Bước này chính là trái tim của Quicksort.
Đệ quy (Recursively Sort): Áp dụng đệ quy thuật toán Quicksort cho mảng con bên trái của chốt và mảng con bên phải của chốt.

Bước kết hợp không cần thiết trong Quicksort vì sau khi các mảng con được sắp xếp đệ quy, toàn bộ mảng sẽ tự động được sắp xếp.

Đi sâu vào Phân hoạch (Partitioning)

Bước phân hoạch là phần phức tạp nhất và quan trọng nhất để hiểu Quicksort. Có nhiều cách để thực hiện phân hoạch, nhưng một trong những cách phổ biến và dễ hiểu là Partitioning theo kiểu Lomuto.

Giả sử chúng ta chọn phần tử cuối cùng của mảng (hoặc mảng con) làm chốt. Quá trình phân hoạch diễn ra như sau:

Chúng ta duy trì một chỉ số i (ban đầu là low - 1, với low là chỉ số bắt đầu của mảng con). Chỉ số i này sẽ trỏ đến vị trí cuối cùng của dãy các phần tử nhỏ hơn hoặc bằng chốt mà chúng ta đã tìm thấy cho đến hiện tại.
Chúng ta duyệt qua mảng từ chỉ số low đến high - 1 (với high là chỉ số cuối cùng của mảng con, nơi chứa chốt). Sử dụng chỉ số j cho vòng lặp này.
Với mỗi phần tử arr[j]:
- Nếu arr[j] nhỏ hơn hoặc bằng chốt, điều đó có nghĩa là nó thuộc về phần bên trái của chốt. Chúng ta tăng i lên 1 (++i) và hoán đổi (swap) arr[i] với arr[j]. Việc này đảm bảo rằng các phần tử nhỏ hơn chốt luôn được đẩy về phía đầu mảng con (sau vị trí i).
Sau khi duyệt hết mảng con (trừ chốt), tất cả các phần tử nhỏ hơn hoặc bằng chốt đã được đưa về các vị trí từ low đến i. Các phần tử lớn hơn chốt nằm ở các vị trí từ i+1 đến high-1.
Cuối cùng, chúng ta đặt chốt vào vị trí đúng của nó bằng cách hoán đổi arr[i + 1] với arr[high] (chính là chốt). Vị trí i + 1 lúc này là vị trí đầu tiên mà một phần tử lớn hơn chốt có thể nằm, hoặc nếu không có phần tử nào lớn hơn, nó là vị trí ngay sau phần tử lớn nhất nhỏ hơn chốt.
Hàm phân hoạch trả về chỉ số của chốt sau khi đã đặt đúng vị trí (i + 1).

Lựa chọn Chốt (Pivot Selection)

Việc chọn chốt ảnh hưởng lớn đến hiệu suất của Quicksort.

Chọn phần tử đầu tiên hoặc cuối cùng: Đơn giản để triển khai, nhưng nếu mảng đầu vào đã được sắp xếp hoặc gần sắp xếp, cách chọn này sẽ dẫn đến trường hợp xấu nhất (O(n^2)).
Chọn ngẫu nhiên: Chọn một phần tử ngẫu nhiên trong mảng con làm chốt. Điều này giúp giảm thiểu khả năng gặp phải trường hợp xấu nhất trên các dữ liệu đầu vào có cấu trúc cụ thể.
Chọn Median-of-Three: Chọn giá trị trung vị (median) của ba phần tử (ví dụ: phần tử đầu, giữa và cuối) làm chốt. Cách này thường cho hiệu suất tốt hơn trong thực tế.

Trong ví dụ code dưới đây, chúng ta sẽ sử dụng cách đơn giản nhất: chọn phần tử cuối cùng làm chốt để minh họa rõ ràng cơ chế phân hoạch Lomuto.

Cài đặt Quicksort trong C++

Chúng ta cần các hàm sau:

swap: Hàm tiện ích để hoán đổi hai phần tử. May mắn thay, thư viện chuẩn C++ cung cấp swap.
partition: Hàm thực hiện bước phân hoạch, nhận mảng/vector, chỉ số bắt đầu (low), chỉ số kết thúc (high) và trả về chỉ số của chốt sau khi phân hoạch.
quickSort: Hàm chính thực hiện sắp xếp đệ quy.

Đây là mã nguồn C++ minh họa:

#include <iostream> // Để sử dụng cout
#include <vector>   // Để sử dụng vector
#include <utility>  // Để sử dụng swap

// Hàm tiện ích để in vector
void printVector(const vector<int>& arr) {
    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;
}

// Hàm thực hiện phân hoạch (kiểu Lomuto)
// arr: vector cần phân hoạch
// low: chỉ số bắt đầu của mảng con
// high: chỉ số kết thúc của mảng con (nơi chứa pivot ban đầu)
// Trả về chỉ số của pivot sau khi phân hoạch
int partition(vector<int>& arr, int low, int high) {
    // Chọn phần tử cuối cùng làm pivot
    int pivot = arr[high];

    // Chỉ số của phần tử nhỏ hơn
    // Biểu thị vị trí cuối cùng của dãy các phần tử <= pivot
    int i = (low - 1); 

    // Duyệt qua tất cả các phần tử từ low đến high-1
    for (int j = low; j <= high - 1; j++) {
        // Nếu phần tử hiện tại nhỏ hơn hoặc bằng pivot
        if (arr[j] <= pivot) {
            // Tăng chỉ số của phần tử nhỏ hơn
            i++; 
            // Hoán đổi phần tử hiện tại với phần tử tại vị trí i
            // Điều này đưa các phần tử nhỏ hơn về phía đầu mảng con
            swap(arr[i], arr[j]);
        }
    }

    // Đặt pivot vào đúng vị trí của nó
    // Hoán đổi pivot (đang ở arr[high]) với phần tử ngay sau vị trí i
    swap(arr[i + 1], arr[high]);

    // Trả về chỉ số của pivot sau khi đã đặt đúng chỗ
    return (i + 1);
}

// Hàm chính thực hiện QuickSort
// arr: vector cần sắp xếp
// low: chỉ số bắt đầu của mảng con
// high: chỉ số kết thúc của mảng con
void quickSort(vector<int>& arr, int low, int high) {
    // Điều kiện dừng đệ quy: khi mảng con có 0 hoặc 1 phần tử
    if (low < high) {
        // pi là chỉ số phân hoạch, arr[pi] đã đúng vị trí
        int pi = partition(arr, low, high);

        // Sắp xếp đệ quy các phần tử trước và sau chỉ số phân hoạch
        quickSort(arr, low, pi - 1);  // Sắp xếp mảng con bên trái pivot
        quickSort(arr, pi + 1, high); // Sắp xếp mảng con bên phải pivot
    }
}

// Hàm main để kiểm tra
int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();

    cout << "Mang truoc khi sap xep: ";
    printVector(arr);

    quickSort(arr, 0, n - 1);

    cout << "Mang sau khi sap xep:  ";
    printVector(arr);

    // Một ví dụ khác
    vector<int> arr2 = {4, 2, 7, 1, 3, 6, 5};
    int n2 = arr2.size();

    cout << "\nMang truoc khi sap xep: ";
    printVector(arr2);

    quickSort(arr2, 0, n2 - 1);

    cout << "Mang sau khi sap xep:  ";
    printVector(arr2);

    return 0;
}

Giải thích Code

Hàm printVector: Đây là một hàm trợ giúp đơn giản để hiển thị nội dung của vector<int>. Nó duyệt qua từng phần tử và in ra, sau đó xuống dòng. Sử dụng const& để tránh sao chép vector không cần thiết.
Hàm partition(vector<int>& arr, int low, int high):
- Tham số arr: Vector cần thao tác (truyền tham chiếu để có thể thay đổi).
- Tham số low, high: Chỉ số bắt đầu và kết thúc của đoạn mảng con hiện tại cần phân hoạch.
- int pivot = arr[high];: Chọn phần tử cuối cùng của đoạn làm chốt.
- int i = (low - 1);: Khởi tạo chỉ số i. Vị trí i+1 sẽ là nơi chúng ta đặt chốt vào cuối hàm. Ban đầu, i nằm ngoài đoạn hợp lệ (low đến high) và nhỏ hơn low.
- for (int j = low; j <= high - 1; j++): Vòng lặp chính duyệt từ đầu đoạn (low) đến trước phần tử chốt (high-1).
- if (arr[j] <= pivot): Nếu phần tử hiện tại arr[j] nhỏ hơn hoặc bằng chốt:
  - i++;: Tăng i lên. Lúc này i trỏ đến vị trí đầu tiên trong đoạn mà chúng ta chưa chắc đó là phần tử nhỏ hơn chốt.
  - swap(arr[i], arr[j]);: Hoán đổi arr[i] với arr[j]. Điều này đưa arr[j] (phần tử nhỏ hơn chốt) vào vị trí i, đảm bảo rằng tất cả các phần tử từ low đến i đều nhỏ hơn hoặc bằng chốt.
- swap(arr[i + 1], arr[high]);: Sau vòng lặp, tất cả các phần tử từ low đến i nhỏ hơn hoặc bằng chốt. Các phần tử từ i+1 đến high-1 lớn hơn chốt. Hoán đổi chốt (đang ở arr[high]) với phần tử tại arr[i+1] để đặt chốt vào vị trí phân hoạch chính xác.
- return (i + 1);: Trả về chỉ số của chốt sau khi nó đã được đặt đúng vị trí.
Hàm quickSort(vector<int>& arr, int low, int high):
- Tham số arr: Vector cần sắp xếp (truyền tham chiếu).
- Tham số low, high: Chỉ số bắt đầu và kết thúc của đoạn mảng con hiện tại cần sắp xếp.
- if (low < high): Đây là điều kiện dừng đệ quy. Nếu low >= high, đoạn mảng con chỉ có 0 hoặc 1 phần tử, đã được sắp xếp, nên dừng lại.
- int pi = partition(arr, low, high);: Gọi hàm phân hoạch để chia đoạn mảng con hiện tại và lấy về chỉ số của chốt (pi).
- quickSort(arr, low, pi - 1);: Gọi đệ quy để sắp xếp đoạn mảng con bên trái chốt (từ low đến pi - 1).
- quickSort(arr, pi + 1, high);: Gọi đệ quy để sắp xếp đoạn mảng con bên phải chốt (từ pi + 1 đến high).
Hàm main:
- Khởi tạo một vector<int> mẫu.
- In vector trước khi sắp xếp.
- Gọi quickSort trên vector, với low = 0 và high = n - 1 (toàn bộ vector).
- In vector sau khi sắp xếp để kiểm tra kết quả.
- Thêm một ví dụ khác để minh họa.

Phân tích Hiệu suất (Complexity Analysis)

Hiệu suất của Quicksort phụ thuộc nhiều vào việc lựa chọn chốt và cách phân hoạch chia mảng.

Trường hợp Tốt nhất (Best Case): O(n log n)
- Xảy ra khi mỗi lần phân hoạch, chốt luôn chia mảng/mảng con thành hai nửa có kích thước gần bằng nhau.
- Độ sâu của cây đệ quy là O(log n). Mỗi cấp của cây đệ quy thực hiện tổng cộng O(n) công việc (duyệt và hoán đổi).
- Tổng cộng: O(n log n).
Trường hợp Trung bình (Average Case): O(n log n)
- Ngay cả khi việc chia mảng không hoàn hảo, nếu chốt không liên tục là phần tử nhỏ nhất hoặc lớn nhất, Quicksort vẫn cho hiệu suất rất tốt.
- Trong thực tế, Quicksort thường là một trong những thuật toán sắp xếp dựa trên so sánh nhanh nhất do các hằng số nhỏ trong thời gian thực thi.
Trường hợp Xấu nhất (Worst Case): O(n^2)
- Xảy ra khi mỗi lần phân hoạch, chốt luôn là phần tử nhỏ nhất hoặc lớn nhất trong mảng con. Điều này dẫn đến việc một mảng con có kích thước N-1 và mảng con còn lại có kích thước 0.
- Độ sâu của cây đệ quy trở thành O(n). Mỗi cấp vẫn cần O(n) công việc.
- Tổng cộng: O(n^2).
- Tình huống này xảy ra với cách chọn chốt là phần tử đầu/cuối nếu mảng đầu vào đã được sắp xếp hoặc đảo ngược.
Độ phức tạp không gian (Space Complexity):
- Quicksort là một thuật toán sắp xếp tại chỗ (in-place), có nghĩa là nó chỉ sử dụng một lượng bộ nhớ nhỏ phụ trợ ngoài bộ nhớ lưu trữ mảng.
- Không gian cần thiết chủ yếu là cho ngăn xếp đệ quy.
- Trường hợp Tốt nhất/Trung bình: O(log n) (độ sâu cây đệ quy).
- Trường hợp Xấu nhất: O(n) (độ sâu cây đệ quy tuyến tính).

Tại sao Quicksort phổ biến?

Mặc dù có trường hợp xấu nhất là O(n^2), Quicksort vẫn rất phổ biến vì:

Hiệu suất trung bình rất tốt: Trong hầu hết các trường hợp thực tế, Quicksort nhanh hơn các thuật toán O(n log n) khác như Mergesort do constant factor nhỏ.
Tại chỗ (In-place): Nó không yêu cầu thêm bộ nhớ đáng kể ngoài bộ nhớ của mảng ban đầu (không như Mergesort cần O(n) không gian phụ).
Cache-friendly: Cách truy cập bộ nhớ tuần tự trong bước phân hoạch giúp tận dụng tốt cache của CPU.

Bài tập ví dụ: C++ Bài 9.B4: Dãy số tăng

Cho dãy số nguyên dương gồm \(n\) phần tử \(a_1, a_2,..., a_n\). Bạn có thể sử dụng bao nhiêu thao tác tùy ý (có thể không dùng) để thay đổi các phần tử của dãy.

Với một thao tác bạn được chọn hai số \([l, r]\) bất kì sao cho \(1\leq l < r\leq n\), và đảo ngược vị trí của các phần tử trong đoạn từ \(l\) đến \(r\) đó. Nói cách khác, bạn có thể biến đổi dãy con \([a_l, a_{l+1},..., a_r]\) thành \([a_r, a_{r-1},... a_l]\) trong một thao tác.

Ví dụ: Cho \(n = 5\) và dãy \([1, 4, 2, 3, 5]\), chọn \(l = 2\) và \(r = 4\), sau khi biến đổi dãy sẽ được đổi thành \([1, 3, 2, 4, 5]\).

Nhiệm vụ của bạn là kiểm tra xem dãy số đã cho có thể biến đổi thành dãy tăng sau một vài thao tác không.

INPUT FORMAT

Dòng đầu tiên chứa một số nguyên \(t\ (1\leq t\leq 10^4)\) - số lượng test.

Dòng đầu tiên của mỗi test chứa một số nguyên \(n\ (1\leq n\leq 20)\) - độ dài của dãy.

Dòng thứ hai của mỗi test chứa \(n\) số nguyên \(a_1, a_2,... a_n\ (1\leq a_i\leq 10^9)\) - các phần tử của dãy.

OUTPUT FORMAT

In ra \(t\) dòng, mỗi dòng là kết quả của mỗi testcase. Nếu dãy đã cho thỏa mãn in ra YES, ngược lại in ra NO.

Ví dụ:

Input

2
5
1 4 2 3 5
6
10 9 8 8 2 1

Output

YES
NO

Giải thích ví dụ mẫu

Ví dụ 1:
- Dữ liệu: n = 5, dãy [1, 4, 2, 3, 5]
- Giải thích: Bạn có thể chọn đoạn từ vị trí 2 đến 4 và đảo ngược nó để biến dãy thành [1, 3, 2, 4, 5], dãy này đã được sắp xếp tăng dần.
Ví dụ 2:
- Dữ liệu: n = 6, dãy [10, 9, 8, 8, 2, 1]
- Giải thích: Dù bạn có thực hiện các thao tác đảo ngược, không thể sắp xếp dãy này thành dãy tăng dần.

Bạn cần kiểm tra xem dãy có thể trở thành dãy tăng dần sau một số thao tác đảo ngược không.

<br>

1. Phân tích bài toán và ràng buộc:

Mục tiêu: Biến đổi dãy ban đầu thành dãy tăng dần nghiêm ngặt (ví dụ: 1 2 3 4 5, không có phần tử trùng lặp liền kề).
Thao tác: Đảo ngược một đoạn con [l, r] bất kỳ. Có thể sử dụng bao nhiêu thao tác tùy ý (kể cả 0).
Ràng buộc: n rất nhỏ (1 <= n <= 20), t rất lớn (1 <= t <= 10^4). Giá trị phần tử lên đến 10^9.

2. Suy luận hướng giải:

Đích đến duy nhất: Nếu một dãy có thể biến đổi thành dãy tăng dần nghiêm ngặt, thì dãy tăng dần đó phải chứa chính xác các phần tử của dãy ban đầu, được sắp xếp theo thứ tự tăng dần. Thao tác đảo ngược chỉ thay đổi vị trí, không thêm, bớt hay thay đổi giá trị phần tử.
Điều kiện cần: Từ nhận xét trên, điều kiện cần đầu tiên là dãy ban đầu khi được sắp xếp phải tạo thành một dãy tăng dần nghiêm ngặt. Điều này có nghĩa là tất cả các phần tử trong dãy ban đầu phải là duy nhất (distinct). Nếu có phần tử trùng lặp, không thể tạo thành dãy tăng dần nghiêm ngặt.
Kiểm tra khả năng biến đổi: Nếu dãy ban đầu chứa các phần tử duy nhất, thì dãy đã sắp xếp tăng dần chính là đích đến. Ta cần kiểm tra xem có thể đạt được dãy này bằng các thao tác đảo ngược hay không.
Số lượng thao tác: Ràng buộc N <= 20 và T <= 10^4 gợi ý rằng giải pháp cho mỗi test case phải rất hiệu quả, khả năng cao là O(N) hoặc O(N log N), không thể là O(N^2) cho việc thử mọi đoạn đảo ngược nếu cần nhiều thao tác. Điều này dẫn đến giả thuyết rằng nếu dãy có thể sắp xếp được, thì có thể chỉ cần một thao tác đảo ngược đặc biệt để đưa nó về dạng sắp xếp.
Thao tác "đặc biệt": Thao tác đảo ngược duy nhất có khả năng sắp xếp toàn bộ dãy mà không làm hỏng các phần tử đã đúng vị trí là thao tác đảo ngược chính xác cái đoạn con mà các phần tử đang bị sai vị trí so với dãy đã sắp xếp.

3. Các bước thực hiện (Hướng giải chi tiết):

Đọc input: Đọc số lượng test t. Vòng lặp t lần.
Với mỗi test case:
- Đọc số nguyên n.
- Đọc n số nguyên vào một vector<long long> (vì giá trị phần tử có thể lớn). Gọi vector này là a.
- Tạo một bản sao của a, gọi là sorted_a.
- Sắp xếp sorted_a bằng sort.
- Kiểm tra điều kiện cần (phần tử duy nhất): Duyệt qua sorted_a, kiểm tra xem có bất kỳ hai phần tử liền kề nào bằng nhau không (sorted_a[i] == sorted_a[i+1]). Nếu có, in ra NO và chuyển sang test case tiếp theo. (Cách khác: Dùng unique và kiểm tra kích thước, hoặc dùng is_sorted với < operator).
- Tìm đoạn con sai lệch:
  - Tìm chỉ số l (0-based index) đầu tiên mà a[l] != sorted_a[l]. Duyệt từ đầu mảng.
  - Nếu không tìm thấy l (tức là a đã giống hệt sorted_a), dãy ban đầu đã tăng dần, in ra YES.
  - Nếu tìm thấy l, tìm chỉ số r (0-based index) cuối cùng mà a[r] != sorted_a[r]. Duyệt từ cuối mảng về.
- Thực hiện đảo ngược "thử":
  - Tạo một bản sao của dãy a, gọi là temp_a.
  - Đảo ngược đoạn con từ chỉ số l đến r (bao gồm cả l và r) trong temp_a. Sử dụng reverse(temp_a.begin() + l, temp_a.begin() + r + 1).
- Kiểm tra kết quả đảo ngược:
  - So sánh temp_a với sorted_a. Nếu chúng giống hệt nhau, điều đó có nghĩa là chỉ cần một thao tác đảo ngược đoạn [l, r] đã làm cho dãy trở thành tăng dần nghiêm ngặt. In ra YES.
  - Nếu temp_a khác với sorted_a, in ra NO.
- (Lưu ý về ví dụ 1: Có vẻ giải thích trong ví dụ mẫu về dãy kết quả sau đảo ngược là [1, 3, 2, 4, 5] và nói rằng nó tăng dần là một sự nhầm lẫn. Hãy bám sát định nghĩa dãy tăng dần nghiêm ngặt và kiểm tra với dãy đã sắp xếp đúng [1, 2, 3, 4, 5].)

4. Sử dụng các hàm chuẩn của C++ (std):

#include <iostream>: Để đọc/ghi input/output.
#include <vector>: Để sử dụng vector cho dãy số.
#include <algorithm>: Chứa sort, reverse, is_sorted (có thể dùng để kiểm tra nghiêm ngặt).
#include <numeric>: Có thể dùng cho các mục đích khác nhưng không bắt buộc cho hướng giải này.
Kiểm tra nghiêm ngặt có thể dùng vòng lặp hoặc is_sorted kết hợp với lambda function hoặc custom comparator nếu cần kiểm tra không chỉ tăng dần mà còn nghiêm ngặt, nhưng cách đơn giản nhất là dùng vòng lặp for kiểm tra sorted_a[i] >= sorted_a[i+1].
So sánh hai vector có thể dùng toán tử ==.

5. Cấu trúc code tổng quát:

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // Not strictly necessary but good practice

void solve() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (n == 1) { // Base case N=1 is always sorted
        cout << "YES\n";
        return;
    }

    vector<long long> sorted_a = a;
    sort(sorted_a.begin(), sorted_a.end());

    // Check if sorted_a is strictly increasing (i.e., no duplicates)
    bool strictly_increasing = true;
    for (int i = 0; i < n - 1; ++i) {
        if (sorted_a[i] >= sorted_a[i + 1]) { // Use >= to catch duplicates or non-strictly increasing
            strictly_increasing = false;
            break;
        }
    }

    if (!strictly_increasing) {
        cout << "NO\n";
        return;
    }

    // Find the first and last mismatch indices
    int l = -1, r = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i] != sorted_a[i]) {
            if (l == -1) {
                l = i;
            }
            r = i;
        }
    }

    // If no mismatch, array is already sorted
    if (l == -1) {
        cout << "YES\n";
        return;
    }

    // Create a copy and reverse the segment [l, r]
    vector<long long> temp_a = a;
    reverse(temp_a.begin() + l, temp_a.begin() + r + 1);

    // Check if the reversed array is equal to the sorted array
    if (temp_a == sorted_a) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.