Lưu ý rằng giá trị chính xác của \(a_i\) không quan trọng: đối với bất kỳ hai loại hàng hóa nào, ta chỉ cần biết liệu chúng giống nhau hay khác nhau. Do đó, ta thực hiện nén tọa độ, tức là thay thế tất cả \(a_i\) bằng \(b_i\) sao cho với mọi cặp vị trí \(i, j\), nếu \(a_i = a_j\) thì \(b_i = b_j\), đồng thời \(\max(b_i) < n\).

Làm thế nào để kiểm tra xem kệ hàng đã được sắp xếp đúng cách hay chưa? Việc này có thể thực hiện bằng kỹ thuật hai con trỏ. Dưới đây là đoạn mã minh họa:

bool check(vector<int>& b){
    int n = b.size(); 
    vector<int> used(n); 
    for (int i = 0; i < n; ) {
        int j = i; 
        while (i < n && b[i] == b[j]) {
            i++; 
        }
        if (used[b[j]]) {
            return false; 
        }
        used[b[j]] = true; 
    }
    return true;
}

Điều này giúp ích gì cho chúng ta?

Hãy xét một kệ hàng đã được sắp xếp đúng và thực hiện một thao tác hoán đổi. Khi đó, với bất kỳ giá trị nào, số lượng khối chứa giá trị đó sau khi hoán đổi có thể tăng lên tối đa là \(3\).

Thật vậy, nếu ta di chuyển một phần tử từ giữa một khối, khối đó có thể bị tách thành hai phần, và bản thân phần tử được di chuyển có thể tạo thành một khối nữa ở vị trí khác. Do đó, có thể xuất hiện tối đa \(3\) khối.

Vì thao tác hoán đổi có tính thuận nghịch, ta rút ra một hệ quả quan trọng: nếu có thể thu được một kệ hàng sắp xếp đúng từ mảng hiện tại chỉ bằng một lần hoán đổi, thì trong mảng hiện tại, không có giá trị nào xuất hiện trong hơn \(3\) khối.

Hãy tìm một giá trị \(x\) trong mảng \(b\) sao cho số lượng khối chứa giá trị này lớn hơn \(1\). Nếu số lượng khối của giá trị này lớn hơn \(3\), ta có thể kết luận ngay là "NO" (không thể). Có thể thấy rằng nếu tìm được một phần tử \(x\) như vậy, thì trong một lần hoán đổi thành công, một trong các vị trí tham gia hoán đổi bắt buộc phải chứa giá trị \(x\). Nếu không, vị trí của tất cả các phần tử có giá trị \(x\) sẽ không thay đổi, và do đó các khối chứa giá trị \(x\) vẫn sẽ bị tách rời thành nhiều khối riêng biệt.

Hơn nữa, đối với mỗi khối chứa giá trị \(x\), việc chọn một vị trí nằm ở giữa khối là không mang lại hiệu quả. Nếu ta hoán đổi một phần tử nằm giữa khối với một phần tử khác, khối đó sẽ bị chia cắt thành hai phần. Vì vậy, ta chỉ cần xét các vị trí ở hai đầu mút của mỗi khối chứa giá trị \(x\) làm các ứng viên tiềm năng.

Có tối đa \(3 \times 2 = 6\) ứng viên như vậy, vì có tối đa \(3\) khối chứa giá trị \(x\).

Một quan sát tiếp theo là cũng chỉ có một số ít ứng viên cho vị trí (chỉ số) thứ hai trong phép hoán đổi. Để hợp nhất các khối chứa giá trị \(x\), vị trí thứ hai phải nằm gần một trong các khối này—cụ thể là ngay bên trái hoặc ngay bên phải của một khối nào đó. Nếu không, ta sẽ không thể đưa tất cả các phần tử có giá trị \(x\) về cùng một khối liên tục.

Cũng có tối đa \(6\) ứng viên cho vị trí này.

Như vậy, ta chỉ cần thử một số lượng phép hoán đổi cố định: một vị trí được chọn từ các đầu mút của các khối chứa giá trị \(x\), và vị trí còn lại được chọn từ các vị trí nằm kề các khối đó. Sau mỗi lần hoán đổi, ta kiểm tra xem các phần tử trên kệ đã được sắp xếp đúng hay chưa. Ta có thể thực hiện việc kiểm tra này với độ phức tạp O(n).

Trong quá trình cài đặt, ta có thể đơn giản là đưa tất cả các vị trí dạng \(l − 1, l, r, r + 1\) (ứng với mỗi khối \([l, r]\) chứa giá trị $x) vào một danh sách ứng viên và thử tất cả các cặp vị trí từ danh sách này. Vì có tối đa \(3\) khối, nên có tối đa \(12\) ứng viên; do đó, số lượng phép hoán đổi cần kiểm tra là một hằng số.

Nhìn chung, thuật toán hoạt động với độ phức tạp O(n log n) nhờ vào kỹ thuật nén tọa độ.
Code mẫu C++:

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    auto b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    for (int i = 0; i < n; i++){
        a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
    }
    vector<vector<int>> blocks(n);
    vector<int> cntb(n);
    for (int i = 0; i < n; ){
        int j = i;
        while(i < n && a[i] == a[j]){
            i++;
        }
        blocks[a[j]].push_back(i);
        blocks[a[j]].push_back(i - 1);
        blocks[a[j]].push_back(j);
        blocks[a[j]].push_back(j - 1);
        cntb[a[j]]++;
    }
    auto check = [&](int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= n){
            return 0;
        }
        swap(a[x], a[y]);
        vector<int> cnt(n);
        for (int i = 0; i < n;){
            int j = i;
            while(i < n && a[i] == a[j]){
                i++;
            }
            cnt[a[j]]++;
        }
        swap(a[x], a[y]);
        for (int i = 0; i < n; i++){
            if (cnt[i] > 1){
                return 0;
            }
        }
        return 1;
    };
    for (int i = 0; i < n; i++){
        if (cntb[i] > 1){
            if (cntb[i] > 3){
                cout << "NO\n";
                return;
            }
            bool ok = 0;
            sort(blocks[i].begin(), blocks[i].end());
            blocks[i].erase(unique(blocks[i].begin(), blocks[i].end()), blocks[i].end());
            for (int x : blocks[i]){
                for (int y : blocks[i]){
                    if (x < y){
                        ok |= check(x, y);
                    }
                }
            }
            if (!ok){
                cout << "NO\n";
                return;
            }
            break;
        }
    }
    cout << "YES\n";
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tests = 1;
    cin >> tests;
    while(tests--){
        solve();
    }
    return 0;
}