Editorial for reverse: Đảo ngược xâu

Hiểu bài toán

Bài toán yêu cầu đảo ngược một xâu con liên tiếp của xâu s nhiều lần. Xâu s có độ dài n, các ký tự được đánh số từ 1 đến n. Mỗi lần đảo được đặc tả bởi số ai, tương ứng với việc đảo ngược xâu con từ vị trí ai đến vị trí n - a_i + 1. Ta cần tìm xâu s sau khi thực hiện m lần đảo này theo thứ tự.

Ví dụ: s = "abcdef", n = 6. Nếu a_i = 2, ta đảo xâu con từ 2 đến 6-2+1 = 5, tức là "bcde". Xâu trở thành "aedcbf".

Quan sát thấy các thao tác đảo ngược này chỉ ảnh hưởng đến các cặp ký tự đối xứng qua tâm (i, n-i+1). Cụ thể, một lần đảo với tham số a sẽ lật ngược thứ tự của các cặp từ i = a đến n - a + 1. Nếu một cặp (i, n-i+1) bị lật một số lẻ lần, vị trí của hai ký tự trong cặp này sẽ bị hoán đổi. Nếu số lần lật là chẵn, chúng trở về vị trí ban đầu.

Vấn đề cốt lõi là đếm số lần mỗi cặp đối xứng bị lật. Do số lần lật của một cặp phụ thuộc vào số lượng ai thỏa mãn ai <= i (vì mỗi lần lật ai lặp lại từ ai đến n-a_i+1, nên cấu trúc tương tự như bài toán "cộng dồn" trên mảng).

Các ràng buộc: n <= 200,000, m <= 100,000. Giải thuật cần chạy trong thời gian O(n + m).

Các cách tiếp cận

Cách Mô phỏng trực tiếp (Brute Force)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    string s;
    cin >> s;
    int m;
    cin >> m;

    for (int k = 0; k < m; ++k) {
        int a;
        cin >> a;
        // Chuyển về chỉ số 0-based
        int l = a - 1;
        int r = s.length() - a;
        // Đảo ngược xâu con từ l đến r
        while (l < r) {
            swap(s[l], s[r]);
            l++;
            r--;
        }
    }

    cout << s << endl;
    return 0;
}

• Time Complexity: O(m * n)
• Space Complexity: O(1)

Giải thuật này mô phỏng chính xác quá trình đảo xâu. Với mỗi lần thao tác ai, ta xác định khoảng [ai-1, n-a_i] và thực hiện đảo ngược trực tiếp trên xâu s.

• Độ phức tạp thời gian: Với m lần đảo, mỗi lần mất O(n) (độ dài đoạn cần đảo), tổng thời gian là O(m * n). Với n=200,000 và m=100,000, số thao tác lên tới ~10^10, quá lớn so với giới hạn thời gian (thường là 1s tương đương 10^8 thao tác).
• Độ phức tạp không gian: O(1) nếu không tính xâu đầu vào.

Đây là cách tiếp cận đơn giản nhất nhưng không khả thi do độ phức tạp cao.

Cách Tính toán số lần lật (Prefix Sum)

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;
    int n = s.length();
    int m;
    cin >> m;

    // Mảng đánh dấu (difference array)
    // diff[i] lưu sự thay đổi số lần lật tại vị trí i
    vector<int> diff(n + 2, 0);

    for (int i = 0; i < m; ++i) {
        int a;
        cin >> a;
        // Mỗi lần đảo a, các cặp từ chỉ số a đến n-a+1 bị lật
        // Trong mảng đánh dấu, ta cộng 1 tại a và trừ 1 sau đoạn kết thúc
        diff[a]++;
        diff[n - a + 2]--; // n - a + 1 là vị trí cuối, +2 là sau nó
    }

    // Tính prefix sum để ra số lần lật tại mỗi vị trí
    vector<int> flips(n + 2, 0);
    for (int i = 1; i <= n; ++i) {
        flips[i] = flips[i - 1] + diff[i];
    }

    // Xây dựng xâu kết quả
    string res(n, ' ');
    for (int i = 1; i <= n; ++i) {
        // Nếu số lần lật tại vị trí i là lẻ, ký tự sẽ bị đẩy về vị trí đối xứng
        // Ban đầu s[i-1] thuộc về vị trí i. Nếu lật lẻ, nó sẽ đi về vị trí n-i+1.
        if (flips[i] % 2 == 1) {
            res[n - i] = s[i - 1];
        } else {
            res[i - 1] = s[i - 1];
        }
    }

    cout << res << endl;
    return 0;
}

• Time Complexity: O(n + m)
• Space Complexity: O(n)

Giải thuật sử dụng kỹ thuật "Difference Array" (mảng chênh lệch) để xử lý các thao tác "cộng dồn".

1. Hiểu bản chất: Xâu s có các cặp đối xứng (i, n-i+1). Khi ta thực hiện đảo với a, tất cả các cặp có chỉ số bên trái >= a đều bị lật.
2. Đánh dấu: Thay vì cập nhật lại xâu, ta dùng mảng diff. Với mỗi thao tác a:
   • Cộng 1 vào diff[a] (bắt đầu lật từ a).
   • Trừ 1 vào diff[n - a + 2] (dừng lật sau n - a + 1).
3. Tính tổng: Duyệt mảng diff để tính prefix sum flips. flips[i] chính xác là số lần cặp thứ i bị lật.
4. Xây dựng kết quả:
   • Nếu flips[i] chẵn: Ký tự tại vị trí i giữ nguyên.
   • Nếu flips[i] lẻ: Ký tự tại vị trí i sẽ đi đến vị trí n-i+1 (chỉ số 0-based là n-i).

• Độ phức tạp thời gian: O(m) để đọc và đánh dấu, O(n) để tính prefix sum và xây dựng xâu kết quả. Tổng O(n + m).
• Độ phức tạp không gian: O(n) để lưu mảng chênh lệch và xâu kết quả.

Đây là giải thuật tối ưu và hiệu quả.

Cách Tối ưu không gian (Prefix Sum trên mảng đếm)

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;
    int n = s.length();
    int m;
    cin >> m;

    // Chỉ cần theo dõi số lần xuất hiện của mỗi a_i
    // Do a_i <= n/2, ta dùng mảng cnt có kích thước n/2 + 1
    vector<int> cnt(n / 2 + 1, 0);
    for (int i = 0; i < m; ++i) {
        int a;
        cin >> a;
        cnt[a]++;
    }

    // Duyệt từ ngoài vào trong để tính tổng số lật hiện tại
    int current_flips = 0;
    for (int i = 1; i <= n / 2; ++i) {
        current_flips += cnt[i];

        // Nếu tổng số lật (từ các a <= i) là lẻ, ta hoán đổi cặp này
        if (current_flips % 2 == 1) {
            swap(s[i - 1], s[n - i]);
        }
    }

    cout << s << endl;
    return 0;
}

• Time Complexity: O(n + m)
• Space Complexity: O(n)

Đây là cách tiếp cận Logic cao hơn, dựa trên việc quan sát tính chất "lũy kế" của các thao tác.

1. Quy luật: Nếu một thao tác có giá trị a được thực hiện, nó lật tất cả các cặp từ a đến n/2.
2. Tổng lũy kế: Khi duyệt i từ 1 đến n/2, tổng số lật hiện tại (current_flips) là tổng số lần xuất hiện của các a <= i.
3. Quyết định hoán đổi:
   • Nếu current_flips là lẻ tại vị trí i, có nghĩa là tổng cộng một số lẻ lần lật đã được áp dụng lên cặp thứ i. Vì vậy, ta cần hoán đổi cặp này.
   • Nếu chẵn, giữ nguyên.
4. Tại sao hiệu quả?: Chỉ cần duyệt một vòng lặp từ 1 đến n/2, không cần mảng prefix sum kích thước n. Logic này phát sinh từ việc nhận thấy rằng một cặp chỉ bị ảnh hưởng bởi các thao tác a <= i.

• Độ phức tạp: O(n + m).
• Không gian: O(n) cho xâu, O(n/2) cho mảng đếm.

Lưu ý: Code mẫu Solution 3 sử dụng biến reverse (tên biến không tốt) để lưu current_flips.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có tính chất đối xứng: Mỗi lần đảo với tham số a chỉ ảnh hưởng đến các cặp đối xứng (i, n-i+1) với i >= a.
• Một cặp bị ảnh hưưởng bởi số lần lật lẻ thì bị hoán đổi, số lần lật chẵn thì giữ nguyên.
• Số lần lật của một vị trí i bằng số lượng thao tác a có giá trị a <= i. Đây là bài toán cộng dồn vùng (Range Update) hoặc đếm lũy kế.

Lỗi thường gặp

• Sử dụng mô phỏng trực tiếp (đảo xâu trong vòng lặp)会导致 Timeout do độ phức tạp O(m*n) quá cao.
• Lầm tưởng về phạm vi ảnh hưởng: Một thao tác a không chỉ lật cặp a, mà lật tất cả các cặp từ a đến n-a+1.
• Sai lệch chỉ số (Off-by-one error): Khi chuyển từ chỉ số 1-based (đề bài) sang 0-based (lập trình), ví dụ: xâu con từ a đến b (1-based) tương ứng với chỉ số [a-1, b-1] (0-based).