Thêm, xóa và đếm tiền tố trên Trie

General
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Quản lý một đa tập hợp các từ (ban đầu rỗng) với $q$ thao tác thuộc một trong ba loại:

  • 1 s: Thêm một bản sao của từ $s$ vào tập hợp.
  • 2 s: Xóa một bản sao của từ $s$ khỏi tập hợp (nếu $s$ hiện không có trong tập hợp thì bỏ qua).
  • 3 p: Đếm số từ hiện có trong tập hợp nhận $p$ làm tiền tố.
Dữ liệu vào

Dòng đầu chứa số nguyên $q$. $q$ dòng tiếp theo, mỗi dòng mô tả một thao tác.

Dữ liệu ra

Với mỗi thao tác loại 3, in ra kết quả trên một dòng.

Ví dụ
Input Output
6
1 apple
1 app
3 ap
2 app
3 ap
3 apple
2
1
1
Giới hạn
  • $1 \le q \le 10^4$
  • Tổng độ dài các xâu $\le 10^5$
Draft saved