展板 - 代码源竞赛平台

题目描述

一块环形展板上按顺序写着 $n$ 个小写英文字母，记为字符串 $S$。从任意一个位置开始，沿固定方向读完一圈，都能得到一个长度为 $n$ 的字符串。这样得到的 $n$ 个字符串就是 $S$ 的 $n$ 个循环位移：分别从第 $1,2,\ldots,n$ 个位置开始读取，读到末尾后接着从开头读取，直到读完 $n$ 个字符。

两个等长字符串称为同构，需要满足以下条件：如果可以按照某个一一对应的规则替换其中一个字符串的字母，使它变成另一个字符串。同一个字母的所有出现都必须替换成同一个字母，不同字母必须替换成不同字母；字母可以替换成它自己。每次比较两个字符串时，可以使用不同的替换规则。

将 $S$ 的这 $n$ 个循环位移按同构关系分成若干类，同构的循环位移属于同一类。

工作人员将对展板进行 $q$ 次修改。每次修改把一个指定位置的字符替换为一个小写英文字母，修改会累积生效。请在每次修改后，求出当前 $S$ 的所有循环位移共有多少个同构类。

输入格式

第一行包含两个正整数 $n,q$，分别表示字符串的长度和修改次数。

第二行包含一个长度为 $n$ 的字符串 $S$，表示展板上最初的字母排列。

接下来 $q$ 行，每行包含一个正整数 $p$ 和一个小写英文字母 $c$，表示将当前 $S$ 的第 $p$ 个字符改为 $c$。

输出格式

输出 $q$ 行，每行一个正整数，第 $i$ 行表示完成前 $i$ 次修改后，当前 $S$ 的所有循环位移的同构类数量。

样例

4 2
abab
4 c
2 a

2
4

3 2
abc
1 c
2 c

3
1

样例解释

样例 1：第一次修改后为 abac。四个循环位移中，abac 与 acab 同构，baca 与 caba 同构，形成两类。

第二次修改后为 aaac，四个循环位移两两不同构。

样例 2：两次修改后的字符串分别为 cbc 和 ccc。

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n\le$	$q \le$
$1$	$20$	$12$	$50$
$2$	$25$	$2000$	$2000$
$3$	$15$	$2\times 10^5$	$20$
$4$	$40$		$2\times 10^5$

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$1\le q\le 2\times 10^5$，$1\le p\le n$。$S$ 中的字符及每次修改中的 $c$ 均为小写英文字母。