1. Tóm tắt đề bài

Cho một danh sách động ban đầu rỗng. Thực hiện ~Q~ thao tác thuộc các loại sau:

• Loại 1 (~1\ x~): Thêm giá trị ~x~ vào cuối danh sách (push_back).
• Loại 2 (~2~): Xóa phần tử ở cuối danh sách (pop_back). Nếu danh sách rỗng thì bỏ qua.
• Loại 3 (~3\ p\ x~): Chèn giá trị ~x~ vào vị trí ~p~ (~1 \le p \le \text{kích thước hiện tại} + 1~).

• Loại 4 (~4\ p~): Xóa phần tử tại vị trí ~p~ (~1 \le p \le \text{kích thước hiện tại}~).

• Dữ liệu vào (Input):

  • Dòng 1: Số nguyên ~Q~ (~1 \le Q \le 5000~).
  • ~Q~ dòng tiếp theo: Mỗi dòng mô tả một thao tác theo quy cách trên.

• Dữ liệu ra (Output):

  • Dòng 1: Số lượng phần tử còn lại sau ~Q~ thao tác.
  • Dòng 2: Danh sách các phần tử còn lại phân tách bằng dấu cách (nếu rỗng thì in ra dòng trống).

2. Phân tích bài toán & Giới hạn

• Giới hạn bài toán:

  • ~Q \le 5000~.
  • Số lượng phần tử trong danh sách tại mọi thời điểm tối đa là ~Q \le 5000~.

• Đánh giá cấu trúc dữ liệu:

  • Thao tác chèn/xóa ở vị trí bất kỳ ~p~ trong mảng động (vector) tốn thời gian ~\mathcal{O}(K)~ với ~K~ là số phần tử hiện có do phải dịch chuyển các phần tử phía sau.
  • Với ~Q \le 5000~, tổng số phép tính trong trường hợp xấu nhất không vượt quá: ~\frac{Q^2}{2} \approx \frac{5000^2}{2} \approx 1.25 \times 10^7 \text{ phép tính}~
  • Giới hạn này hoàn toàn xử lý tức thì trong thời gian ~< 0.05~ giây (thấp hơn nhiều so với mốc ~10^8~ phép tính/giây của máy tính). Do đó, sử dụng cấu trúc std::vector chuẩn của C++ là giải pháp tối ưu, ngắn gọn và cài đặt trực quan nhất.

3. Thuật toán xử lý

• Cấu trúc lưu trữ:

  • Sử dụng một mảng động: vector<int> a;.

• Xử lý từng loại truy vấn:

  1. Loại 1 (~1\ x~):
     • Đọc giá trị ~x~.
     • Thêm vào cuối: a.push_back(x);.
  2. Loại 2 (~2~):
     • Kiểm tra nếu danh sách không rỗng (!a.empty()):
       • a.pop_back();.
  3. Loại 3 (~3\ p\ x~):
     • Đọc vị trí ~p~ và giá trị ~x~.
     • Vì vector đánh chỉ số từ ~0~, vị trí thứ ~p~ ứng với vị trí p - 1 trong iterator:
       • a.insert(a.begin() + p - 1, x);.
  4. Loại 4 (~4\ p~):
     • Đọc vị trí ~p~.
     • Xóa phần tử tại vị trí p - 1:
       • a.erase(a.begin() + p - 1);.

• Xuất kết quả:

  1. Dòng 1: In kích thước a.size() rồi xuống dòng bằng cout << endl;.
  2. Dòng 2: Duyệt từng phần tử trong vector a từ đầu đến cuối và in ra kèm khoảng trắng, kết thúc bằng cout << endl;.

• Độ phức tạp:

  • Thời gian: ~\mathcal{O}(Q^2)~ trong trường hợp xấu nhất, xử lý xong trong ~< 0.05~ giây.
  • Không gian (bộ nhớ): ~\mathcal{O}(Q)~ — Chỉ tốn tối đa khoảng ~20\text{ KB}~ bộ nhớ.

4. Mã nguồn cài đặt (C++)

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

int main() {
    // Tối ưu tốc độ vào/ra chuẩn
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int q;
    cin >> q;

    vector<int> a;

    for (int i = 1; i <= q; i++) {
        int type;
        cin >> type;

        if (type == 1) {
            int x;
            cin >> x;
            a.push_back(x);
        } else if (type == 2) {
            if (!a.empty()) {
                a.pop_back();
            }
        } else if (type == 3) {
            int p, x;
            cin >> p >> x;
            a.insert(a.begin() + p - 1, x);
        } else if (type == 4) {
            int p;
            cin >> p;
            a.erase(a.begin() + p - 1);
        }
    }

    // In số lượng phần tử còn lại
    cout << a.size() << endl;

    // In danh sách các phần tử
    for (int i = 0; i < (int)a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}