Thêm, xóa và đếm tiền tố trên Trie
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề 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$
Community Discussion