Hiểu bài toán

Bài toán mô phỏng việc sao chép một đoạn văn bản vào một vị trí nhất định nhiều lần. Ban đầu có một xâu S. Sau đó có N lượt chơi, mỗi lượt đọc ba số a, b, c, thực hiện thao tác sao chép ký tự từ vị trí a đến b (khoảng từ sau ký tự a đến sau ký tự b) và chèn vào sau vị trí c. Sau mỗi lượt, xâu sẽ được cắt bớt phần nằm sau vị trí M (tức là độ dài xâu không vượt quá M). Mục tiêu là tìm K ký tự đầu tiên của xâu cuối cùng sau khi thực hiện N lượt chơi.

Giả sử:

• Vị trí x nằm giữa các ký tự, ví dụ vị trí 0 là đầu xâu, vị trí len(S) là cuối xâu.
• Khoảng [a, b] là các ký tự từ chỉ số a đến b-1 (theo mô tả 'db' thuộc khoảng 2..4 trong 'abdbe').
• Thao tác copy-paste: lấy đoạn S[a...b-1] chèn vào sau vị trí c.
• Ràng buộc: K nhỏ (≤200), M lớn (≤10^9), N và |S| ban đầu lớn (≤200000).

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

Cách Mô phỏng trực tiếp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void solve_brute() {
    int K, M, N;
    cin >> K >> M;
    string S;
    cin >> S;
    cin >> N;

    while (N--) {
        int a, b, c;
        cin >> a >> b >> c;
        string sub = S.substr(a, b - a);
        S.insert(c, sub);
        if (S.length() > M) S = S.substr(0, M);
    }

    cout << S.substr(0, K) << endl;
}

int main() {
    // solve_brute(); // Commented out to avoid TLE
    return 0;
}

• Time Complexity: O(N * M)
• Space Complexity: O(M)

Cách tiếp cận đơn giản nhất là mô phỏng chính xác quá trình. Xử lý từng lượt chơi: trích xuất chuỗi con từ a đến b, chèn vào vị trí c, và cắt ngắn xâu nếu độ dài vượt quá M. Do M có thể lên tới 10^9, cách này chỉ khả thi với các test có M nhỏ (thuộc 3/7 test).

Cách Lược đồ biến đổi (Sử dụng mảng)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Query {
    int a, b, c;
};

int K, N;
long long M;
vector<Query> queries;
int getIndex(int k) {
    for (int i = N - 1; i >= 0; i--) {
        int len = queries[i].b - queries[i].a;
        if (k < queries[i].c) continue;
        if (k >= queries[i].c + len) k -= len;
        else k = queries[i].a + (k - queries[i].c);
    }
    return k;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> K >> M;
    string S; cin >> S;
    cin >> N;
    queries.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> queries[i].a >> queries[i].b >> queries[i].c;
    }

    for (int i = 0; i < K; i++) {
        int idx = getIndex(i);
        if (idx < S.length()) cout << S[idx];
        else cout << ' ';
    }
    cout << endl;
    return 0;
}

• Time Complexity: O(N * K)
• Space Complexity: O(N)

Thay vì thao tác trên xâu, ta theo dõi nguồn gốc của từng vị trí trong xâu cuối cùng. Với mỗi vị trí i (0 <= i < K), ta duyệt ngược các lượt chơi từ cuối về đầu. Nếu vị trí i nằm trong đoạn được chèn, ta dịch chuyển nó về vị trí tương ứng trong xâu cũ. Nếu nằm trong phần bị đẩy sang phải, ta trừ đi độ dài đoạn chèn. Phương pháp này chỉ tốn O(NK) thay vì O(NM).

Cách Lược đồ biến đổi (Tối ưu với SegTree)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 200005;
struct Node { long long src, len; } tree[4 * MAXN];
int K, N;
long long M;
struct Query { int a, b, c; } qs[MAXN];
string S;

void build(int node, int l, int r) {
    if (l == r) { tree[node] = {l, 1}; return; }
    int mid = (l + r) / 2;
    build(2*node, l, mid); build(2*node+1, mid+1, r);
}

void update(int node, int l, int r, int i, int a, int b, int c) {
    if (l >= c + (b-a)) { tree[node].src += (b-a); return; }
    if (r < c) return;
    if (tree[node].len == 0) return;
    if (l == r) {
        if (tree[node].src >= c) tree[node].src += (b-a);
        return;
    }
    int mid = (l+r)/2;
    update(2*node, l, mid, i, a, b, c);
    update(2*node+1, mid+1, r, i, a, b, c);
}

int main() {
    // Phiên bản này cần tối ưu thêm logic truy vấn
    // Dưới đây là pseudocode cho logic truy vấn
    /*
    for (int i = 0; i < K; i++) {
        int pos = i;
        for (int j = N-1; j >= 0; j--) {
            int len = qs[j].b - qs[j].a;
            if (pos < qs[j].c) continue;
            if (pos >= qs[j].c + len) pos -= len;
            else pos = qs[j].a + (pos - qs[j].c);
            if (pos < 0) break;
        }
        if (pos < S.length()) cout << S[pos];
    }
    */
    return 0;
}

• Time Complexity: O(N log N + K log N)
• Space Complexity: O(N)

Phương pháp này nhận thấy rằng ta chỉ cần biết giá trị của K vị trí đầu tiên. Tuy nhiên, do có thể có các truy vấn chèn vào đầu (c=0), các ký tự ban đầu có thể bị đẩy ra sau. Để xử lý hiệu quả, ta cần một cấu trúc dữ liệu phân đoạn (Segment Tree) để lưu trữ các khoảng và khả năng truy vấn nhanh nguồn gốc của một vị trí. Tuy nhiên, do K rất nhỏ, giải pháp O(N*K) ở trên là đủ tốt và dễ cài đặt hơn. Trong trường hợp K lớn, ta cần dùng SegTree.

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

Bài học kinh nghiệm

• Mục tiêu chỉ là K ký tự đầu tiên, nên ta không cần mô phỏng toàn bộ xâu.
• Duyệt ngược thời gian (từ truy vấn cuối về truy vấn đầu) là cách hiệu quả để tìm ra nguồn gốc của một ký tự trong xâu ban đầu.
• Với K nhỏ (≤200), giải pháp O(N*K) là tối ưu và dễ cài đặt.

Lỗi thường gặp

• Sai lệch trong việc xác định chỉ số (0-based vs 1-based), đặc biệt với khái niệm 'vị trí' và 'khoảng'.
• Xử lý tràn số nguyên khi M rất lớn (10^9), cần dùng kiểu dữ liệu long long.
• Cố gắng lưu trữ toàn bộ xâu trong bộ nhớ khi M lớn dẫn đến TLE/MLE.