Contest Edu #1 - So sánh đuôi

View as PDF

Submit solution

Points: 0.50
Time limit: 2.0s
Memory limit: 512M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho ~n~ xâu kí tự và ~1~ xâu ~S~, ký tự thứ ~i~ được ký hiệu là ~S_i~ (~1\leq i\leq n~).

Có ~q~ thao tác được thực hiện trên ~S~, mỗi thao tác có dạng:

  • ~(x,c)~: biến đổi tất cả kí tự của xâu ~S~ từ vị trí thứ ~x~ trở đi trở thành kí tự ~c~ (thực hiện phép gán ~S_i = c~ với mọi ~x\leq i\leq n~).

Yêu cầu

Sau mỗi thao tác, hãy in ra số lượng xâu trong mảng có thứ tự từ điển nhỏ hẳn hơn xâu ~S~.

Dữ liệu

  • Dòng đầu tiên gồm hai giá trị ~n~ và ~q \ (1 \leq n, q \leq 10^6)~.
  • Dòng thứ hai là xâu ~S~ với tối đa ~10^6~ ký tự là chữ cái Latin viết thường.
  • ~n~ dòng tiếp theo là các xâu kí tự trong mảng, mỗi xâu chỉ chứa chữ cái Latin viết thường và tổng độ dài các xâu không vượt quá ~10^6~.
  • ~q~ dòng cuối cùng là các truy vấn thay đổi dưới dạng ~(x,c)~ với ~x~ là 1 số nguyên dương (~1\leq x\leq n~) và ~c~ là 1 kí tự Latin viết thường, phân biệt bằng dấu cách.

Kết quả

  • Dòng đầu tiên in kết quả bài toán trước khi có các thao tác thay đổi.
  • ~q~ dòng tiếp theo, in kết quả bài toán sau mỗi thao tác thay đổi.

Ví dụ

Sample Input
4 3
anatoly
boris
anatooo
anbbbbu
anba
5 o
3 b
7 x
Sample Output
0
0
2
3
Giải thích

Thao tác 1: ~S="anatooo"~.

Thao tác 2: ~S="anbbbbb"~.

Thao tác 3: ~S="anbbbbx"~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.