solution

Trong nhiều ngôn ngữ (Python, Swift, Objective-C...), bộ thu gom rác dùng kỹ thuật đếm tham chiếu (reference counting): mỗi object có một bộ đếm $rc$ = số tham chiếu đang trỏ tới nó. Khi $rc$ giảm về $0$, object được giải phóng (free) ngay lập tức.

Có $n$ object đánh số từ $1$ đến $n$ (ban đầu $rc_i = 0$ với mọi $i$, chưa object nào được tham chiếu). Có các biến (đặt tên bởi chuỗi chữ/số, phân biệt hoa-thường), ban đầu không trỏ tới object nào. Mô phỏng $m$ thao tác lần lượt:

• SET v o: cho biến $v$ trỏ tới object $o$.
  • Nếu $v$ đang trỏ đúng tới $o$ rồi: không có gì thay đổi.
  • Nếu $v$ đang trỏ tới object khác $o_{cũ} \neq o$: giảm $rc_{o_{cũ}}$ đi $1$ trước (nếu về $0$, giải phóng ngay); sau đó cho $v$ trỏ tới $o$ và tăng $rc_o$ lên $1$.
  • Nếu $v$ chưa trỏ tới object nào: cho $v$ trỏ tới $o$ và tăng $rc_o$ lên $1$.
• CLEAR v: hủy tham chiếu của biến $v$ (đề bài đảm bảo $v$ đang trỏ tới một object). Giảm $rc$ của object đó đi $1$ (giải phóng ngay nếu về $0$).

Yêu cầu: in ra dãy id các object bị giải phóng theo đúng thứ tự thời gian chúng bị giải phóng (mỗi object chỉ giải phóng đúng một lần), và số lượng object còn "sống" ($rc>0$) sau khi thực hiện xong tất cả thao tác.

Ví dụ: $n=3, m=3$: SET a 1, SET b 2, SET a 3 → object $1$ bị giải phóng ngay khi a chuyển sang trỏ tới $3$ (vì $rc_1$ về $0$). Kết quả: dãy giải phóng là 1; số object còn sống là 2.