Tóm tắt đề bài

Cho xâu \(S\) độ dài \(n\) gồm các chữ in hoa A...Z. Thực hiện tuần tự \(q\) lệnh xóa:

• Loại 0: xóa kí tự đầu tiên từ trái sang phải có giá trị từ điển nhỏ nhất trong xâu hiện tại.
• Loại 1: xóa kí tự đầu tiên từ trái sang phải có giá trị từ điển lớn nhất trong xâu hiện tại.

Hãy in ra xâu còn lại sau \(q\) lần xóa.

Phân tích

• \(n \le 2\cdot 10^5\), \(q \le 10^5\) nên không thể mô phỏng trực tiếp mỗi lệnh bằng cách quét toàn bộ xâu (sẽ là \(O(nq)\)).
• Bảng chữ cái chỉ có \(26\) ký tự.
• Mỗi thao tác yêu cầu:
  • Tìm chữ nhỏ nhất/lớn nhất còn tồn tại.
  • Xóa vị trí xuất hiện sớm nhất của chữ đó (tức chỉ số nhỏ nhất).

Nhận xét then chốt:

• Nếu ta lưu với mỗi chữ cái một cấu trúc chứa các vị trí còn “sống” của chữ đó, thì:
  • “kí tự đầu tiên” của chữ đó chính là vị trí nhỏ nhất trong cấu trúc.
  • Chữ nhỏ nhất/lớn nhất còn tồn tại có thể tìm bằng cách duyệt từ A đến Z hoặc ngược lại (chỉ 26 bước).

Vì vậy, mỗi lệnh có thể làm trong \(O(26 + \log n)\), tức gần như \(O(\log n)\).

Hướng giải quyết

Ý tưởng

• Tiền xử lý: với mỗi ký tự \(c \in [0..25]\), lưu tất cả vị trí \(i\) sao cho \(S[i]=c\) vào một set<int> (tự sắp xếp).
• Khi gặp lệnh:
  • Nếu là loại 0:
    1. Duyệt \(c\) từ A đến Z để tìm chữ đầu tiên có set[c] không rỗng.
    2. Lấy vị trí nhỏ nhất pos = *set[c].begin() và xóa nó khỏi set.
  • Nếu là loại 1:
    1. Duyệt \(c\) từ Z về A để tìm chữ đầu tiên còn tồn tại.
    2. Xóa vị trí nhỏ nhất của chữ đó (vẫn là begin() vì yêu cầu “đầu tiên từ trái qua phải”).
• Sau khi xử lý xong \(q\) lệnh, ta cần in xâu còn lại theo thứ tự ban đầu:
  • Duyệt từng vị trí \(i=1..n\), nếu \(i\) còn nằm trong set của ký tự \(S[i]\) thì in ra $S[i]`.
  • Để kiểm tra nhanh, ta có thể dùng mảng alive[i] ban đầu là true, khi xóa thì đặt false.

Thuật toán

1. Đọc \(n, q\), đọc xâu \(S\) (đánh chỉ số từ \(1\) đến \(n\)).
2. Khởi tạo set<int> pos[26].
3. Với mỗi vị trí \(i\):
   • pos[S[i]-'A'].insert(i).
4. Với mỗi lệnh \(t\):
   • Nếu \(t = 0\):
     • Tìm \(c\) nhỏ nhất sao cho pos[c] không rỗng.
     • i = *pos[c].begin(), xóa i và đánh dấu alive[i]=false.
   • Nếu \(t = 1\):
     • Tìm \(c\) lớn nhất sao cho pos[c] không rỗng.
     • i = *pos[c].begin(), xóa i và đánh dấu alive[i]=false.
5. In các ký tự \(S[i]\) với alive[i]=true.

Lưu ý / lỗi hay gặp

• Dù là xóa chữ lớn nhất, vẫn phải xóa lần xuất hiện đầu tiên của chữ đó, nên vẫn lấy phần tử nhỏ nhất trong set (không phải lớn nhất).
• \(q\) có thể gần \(n\), nhưng đề không nói chắc \(q \le n\); thực tế khi xóa quá số ký tự thì không còn gì để xóa. Với bài chuẩn thường có \(q \le n\), nhưng vẫn có thể phòng thủ bằng cách dừng nếu mọi set đều rỗng.

Độ phức tạp

• Mỗi lệnh:
  • Duyệt tối đa \(26\) chữ cái để tìm loại cần xóa.
  • Xóa khỏi set: \(O(\log n)\).
• Tổng:
  • Thời gian: \(O\big(q(26 + \log n) + n\big)\), phù hợp.
  • Bộ nhớ: \(O(n)\).

Code tham khảo

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

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

    int n, q;
    cin >> n >> q;
    string S;
    cin >> S;
    S = " " + S; // 1-index

    array<set<int>, 26> pos;
    vector<char> alive(n + 1, 1);

    for (int i = 1; i <= n; i++) {
        pos[S[i] - 'A'].insert(i);
    }

    for (int k = 0; k < q; k++) {
        int t;
        cin >> t;

        int c = -1;
        if (t == 0) {
            for (int x = 0; x < 26; x++) {
                if (!pos[x].empty()) {
                    c = x;
                    break;
                }
            }
        } else {
            for (int x = 25; x >= 0; x--) {
                if (!pos[x].empty()) {
                    c = x;
                    break;
                }
            }
        }

        // Nếu không còn ký tự nào để xóa (phòng thủ)
        if (c == -1) break;

        int i = *pos[c].begin();   // vị trí xuất hiện sớm nhất
        pos[c].erase(pos[c].begin());
        alive[i] = 0;
    }

    string ans;
    ans.reserve(n);
    for (int i = 1; i <= n; i++) {
        if (alive[i]) ans.push_back(S[i]);
    }

    cout << ans << "\n";
    return 0;
}