1) Tóm tắt đề

Ta có một tài liệu gồm các dòng đánh số ban đầu từ 1 đến N (dòng i chứa số i). Có M thao tác “cắt–dán”; thao tác thứ t (1 ≤ t ≤ M) được cho bởi ba số nguyên (A, B, C):

• Cắt đoạn liên tiếp [A..B] (độ dài len = B − A + 1),
• Xóa đoạn đó khỏi tài liệu,
• Dán đoạn vừa cắt vào sau vị trí C trong tài liệu đã xóa (nếu C = 0 thì dán lên đầu).

Yêu cầu: sau khi thực hiện theo thứ tự M thao tác, hãy in ra 10 dòng đầu của tài liệu thu được (nếu N < 10 thì in N dòng).

2) Ý tưởng & phân tích thuật toán

Gợi ý mấu chốt (đi ngược – “preimage”)

Thay vì “mô phỏng đi tới” toàn bộ tài liệu (N có thể tới $10^5$, M tới $10^3$), ta chỉ quan tâm 10 vị trí đầu tiên cuối cùng: i = 1..min(10, N).
Với mỗi vị trí i ở KẾT QUẢ, ta “lần ngược” các phép cắt–dán từ thao tác M về 1 để tìm ra vị trí nguồn ban đầu (ở tài liệu gốc 1..N) đã di chuyển tới i. Tức là, ta cần một hàm “đi ngược một thao tác”:

Bài toán con: Với một phép cắt–dán (A, B, C) và một vị trí i sau khi dán, hãy xác định vị trí j trước khi cắt (vị trí nào sẽ chuyển tới i sau phép đó).

Công thức “đi ngược” cho một thao tác (A, B, C)

Kí hiệu len = B − A + 1.
Sau khi cắt [A..B], ta có dãy “khung” S gồm N − len phần tử, theo thứ tự:

• Khối 1: 1..A−1 (kích thước A−1),
• Khối 2: B+1..N (kích thước N−B).

Sau đó dán [A..B] vào sau vị trí C của S. Như vậy, dãy cuối gồm:

• Các phần tử S[1..C],
• Rồi đến khối [A..B] (độ dài len),
• Rồi đến S[C+1..].

Với i là vị trí trong dãy cuối, ta xét 3 vùng:

1. i ∈ [C+1, C+len] ⇒ i nằm bên trong khối vừa dán:
   Phần tử thứ i − C của [A..B] tới i, nên: j = A + (i − C) − 1
2. i ≤ C ⇒ i nằm trong đoạn S đầu (trước khi dán):
   Hãy gọi r = i là chỉ số trong S. Phần tử S[r] chính là một phần tử gốc không thuộc [A..B].
   • Nếu r < A thì S[r] = r (vì khối 1 là 1..A−1).
   • Nếu r ≥ A thì S[r] = r + len (vì r “nhảy” qua cả khối bị cắt).
     Tức là: j = (r < A) ? r : (r + len)
3. i > C + len ⇒ i nằm trong đoạn S đuôi (sau khối dán):
   Lúc này i bị “đội” thêm len do khối dán xuất hiện phía trước, nên chỉ số trong S là: r = i − len
   Suy ra: j = (r < A) ? r : (r + len)

Kết luận: một phép “đi ngược” là O(1).
Áp dụng cho mỗi i = 1..10 qua M thao tác (đi ngược) → độ phức tạp O(M · 10), rất nhanh.

Đúng đắn ngắn gọn

• Sau khi cắt, dãy S là dãy ban đầu bỏ đoạn [A..B], giữ thứ tự tương đối.
• Dán vào sau C trong S nghĩa là dãy cuối = S[1..C] + [A..B] + S[C+1..].
• Truy vết preimage theo ba trường hợp trên là đúng theo cấu trúc ghép nối; do mỗi phần tử xuất hiện đúng một lần, ánh xạ là song ánh nên truy ngược từng thao tác là hợp lệ.

3) Lời giải THAM KHẢO (C++, O(M·10))

#include <bits/stdc++.h>
using namespace std;

struct Op {
    int A, B, C;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    if (!(cin >> N >> M)) return 0;
    vector<Op> ops(M);
    for (int i = 0; i < M; ++i) {
        cin >> ops[i].A >> ops[i].B >> ops[i].C;
    }

    int outLines = min(N, 10);
    for (int i = 1; i <= outLines; ++i) {
        long long pos = i; // vị trí hiện tại (sau tất cả thao tác)
        // đi ngược từ thao tác M về 1
        for (int t = M - 1; t >= 0; --t) {
            int A = ops[t].A, B = ops[t].B, C = ops[t].C;
            int len = B - A + 1;

            if (pos >= C + 1 && pos <= C + len) {
                // nằm trong khối dán
                pos = A + (pos - (C + 1));
            } else if (pos <= C) {
                // nằm trong S đầu
                long long r = pos; // chỉ số trong S
                pos = (r < A) ? r : (r + len);
            } else { // pos > C + len
                long long r = pos - len; // chỉ số trong S
                pos = (r < A) ? r : (r + len);
            }
        }
        cout << pos << "\n";
    }
    return 0;
}

Ghi chú triển khai

• Dùng int là đủ ($N ≤ 10^5$), nhưng ta để long long pos để đảm bảo không tràn số khi cộng trừ.
• Nếu N < 10, in ra đúng N dòng đầu như yêu cầu.
• Không cần mô phỏng toàn bộ tài liệu; chỉ cần “preimage” cho mỗi vị trí 1..min(10, N).

4) Độ phức tạp

• Mỗi vị trí chạy qua M thao tác, mỗi thao tác O(1) → O(M · 10) ≈ O(M).
• Bộ nhớ O(M).

5) Kiểm thử nhanh bằng logic

• Với thao tác “không đổi” (ví dụ A=1, B=1, C=0), công thức vẫn hoạt động: đoạn [1..1] bị cắt ra và dán lên đầu → không đổi.
• Trường hợp C = 0 (dán lên đầu) hoặc C = N − len (dán cuối) đều được bao bởi ba nhánh đã xét: biên C+1 và C+len xử lý chính xác phần “khối dán”, còn hai phía là S-đầu / S-đuôi.

6) LINK NỘP BÀI

Sau khi đã xem qua nội dung, bạn có thể thử nộp bài tại đây https://oj.program.edu.vn/problem/cpb_paste