TLEoj Contest #04 - Thao tác trên xâu

Xem PDF
Nộp bài
Điểm: 1500 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 256M
Input: bàn phím
Output: màn hình
Tác giả:
NgVanMinh
Dạng bài

ngvanminh_ có 1 xâu s có độ dài n chỉ gồm các chữ cái thường. Cậu thực hiện q thao tác, thao tác thứ i chứa số nguyên x_i và kí tự c_i: ngvanminh_ sẽ thay đổi kí tự ở vị trí thứ x_i thành c_i.

Nhiệm vụ của bạn là đếm số lượng xâu khác nhau đã được tạo ra sau q thao tác (tính cả xâu ban đầu).

Input, Output và Subtasks

Input
  • Dòng thứ nhất chứa 2 số nguyên dương n,q\ (1\le n,q\le 10^5) - độ dài của xâu và số lượng thao tác.
  • Dòng tiếp theo chứa xâu s có độ dài n chỉ gồm các chữ cái thường.
  • Sau đó là q truy vấn, mỗi truy vấn chứa số nguyên x_i và kí tự c_i\ (1\le x_i\le n).
Output

In ra số lượng xâu khác nhau đã được tạo ra sau q thao tác.

Scoring
  • Subtask 1 (30\%): n\le 20
  • Subtask 2 (70\%): Không có ràng buộc gì thêm

Sample

Input 
3 7
abc
1 n
2 v
3 m
1 a
2 b
3 c
2 b
Output 
6
Note

Các xâu đã tạo được là abc, nbc, nvc, nvm, avm, abm, abc, abc. Trong đó có 6 xâu khác nhau là abc, nbc, nvc, nvm, avm, abm

Bình luận