trang chủ / bài tập / threesub

Ba dãy con rời nhau

Cho một xâu $S$ gồm $n$ chữ cái latin in thường, gọi là văn bản.

Ta theo dõi thêm ba xâu $t_{1}$ , $t_{2}$ , $t_{3}$ ; ban đầu cả ba đều rỗng.

Bộ ba xâu này được gọi là tương thích với văn bản nếu có thể tô màu một số ký tự của $S$ bằng ba màu $1$ , $2$ , $3$ , mỗi ký tự được tô nhiều nhất một màu, sao cho với mọi $i$ , xâu thu được từ $S$ bằng cách chỉ giữ lại các ký tự mang màu $i$ (giữ nguyên thứ tự) đúng bằng $t_{i}$ . Nói cách khác, $t_{1}$ , $t_{2}$ , $t_{3}$ phải là ba dãy con của $S$ đôi một không dùng chung vị trí nào.

Có $q$ thao tác thay đổi, mỗi thao tác thuộc một trong hai dạng:

+ i c: thêm ký tự $c$ vào cuối xâu $t_{i}$ ;
- i: xoá ký tự cuối của xâu $t_{i}$ .

Sau mỗi thao tác, hãy cho biết ba xâu hiện tại có tương thích với văn bản hay không.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $q$ .
Dòng thứ hai chứa xâu $S$ gồm $n$ chữ cái latin in thường.
$q$ dòng tiếp theo, mỗi dòng mô tả một thao tác theo đúng một trong hai dạng + i c hoặc - i.

Dữ liệu ra

Gồm $q$ dòng. Dòng thứ $j$ ghi YES nếu sau thao tác thứ $j$ ba xâu tương thích với văn bản, ngược lại ghi NO.

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq q \leq 1000$
$i \in {1, 2, 3}$ và $c$ là một chữ cái latin in thường
Thao tác - i chỉ xuất hiện khi $t_{i}$ đang khác rỗng
Tại mọi thời điểm, độ dài mỗi xâu $t_{i}$ không vượt quá $250$

Ví dụ

Input	Output	Giải thích
6 8 abbaab + 1 a + 2 a + 3 a + 1 b + 2 b + 3 b - 1 + 2 z	YES YES YES YES YES NO YES NO	Sau thao tác thứ $5$ ta có $t_{1} = a b$ , $t_{2} = a b$ , $t_{3} = a$ : năm ký tự này vừa đủ nằm rời nhau trong abbaab. Thao tác thứ $6$ làm $t_{3} = a b$ ; ba xâu cần đúng ba chữ a và ba chữ b, vừa bằng số lượng có trong abbaab nên bắt buộc phải dùng hết cả sáu vị trí. Ba chữ a nằm ở vị trí $1, 4, 5$ và ba chữ b nằm ở vị trí $2, 3, 6$ , mà hai chữ a ở vị trí $4$ và $5$ chỉ còn đúng chữ b ở vị trí $6$ đứng sau, nên không ghép được ba cặp rời nhau. Thao tác thứ $8$ thêm chữ z không hề xuất hiện trong văn bản.
6 8 abdabc + 1 a + 1 d + 2 b + 2 c + 3 a + 3 b + 1 c - 2	YES YES YES YES YES YES NO YES	Sau thao tác thứ $6$ ta có $t_{1} = a d$ , $t_{2} = b c$ , $t_{3} = a b$ . Đánh số các vị trí của abdabc từ $1$ đến $6$ : tô màu $1$ cho các vị trí $1, 3$ , màu $2$ cho các vị trí $2, 6$ , màu $3$ cho các vị trí $4, 5$ . Thao tác thứ $7$ làm $t_{1} = a d c$ , khi đó cả ba xâu cần tổng cộng bảy ký tự trong khi văn bản chỉ dài sáu.

Bình luận

Không có bình luận tại thời điểm này.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 8,00một phần

Giới hạn thời gian 1.0s

Giới hạn bộ nhớ 256M

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

C++