Từ Điển Động

Buổi 55 — Trie & Aho-Corasick Data-structures
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Quản lý một đa tập hợp (multiset) các từ ban đầu rỗng qua $Q$ truy vấn:

  • 1 S: Thêm một bản sao của từ $S$ vào đa tập hợp.
  • 2 S: Xóa một bản sao của từ $S$ khỏi đa tập hợp (nếu $S$ không có trong đa tập hợp thì bỏ qua).
  • 3 P: Đếm số lượng từ hiện có trong đa tập hợp bắt đầu bằng tiền tố $P$.
Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $Q$ ($1 \le Q \le 10^5$).
  • $Q$ dòng tiếp theo, mỗi dòng gồm loại truy vấn $t \in {1, 2, 3}$ và xâu $S$ (hoặc $P$).
Dữ liệu ra
  • Với mỗi truy vấn loại 3, in ra kết quả trên một dòng.
Ví dụ
Input Output
7
1 apple
1 app
3 ap
2 app
3 ap
2 app
3 ap
2
1
1
Giới hạn
  • Tổng độ dài các xâu không vượt quá $10^6$.
  • Các ký tự đều thuộc a–z.
Draft saved