Problem F
False Sanctum

Kivotos is in deep trouble. Familiar yet different monsters had made their appearance all over Kivotos, guarding what seems to be False Sanctums. The students plan to destroy these sanctums as fast as possible to stop the monster raid.

The hacker group of the Millenium Science School, Veritas, is trying to hack through the fifth False Sanctum’s defenses. The fifth False Sanctum is guarded by Hod, a large robot which was originally the communications unit AI of the Millennium, but was hacked by an unidentified AI and now claims itself to be the eighth prophet of the Decagrammaton.

The documentation states that Hod has a weak spot in its security system, which is represented by a 1-indexed string $S$ of length $N$. The document states that it is possible to project the density of a continuous substring $S[l, r]$ in the following way:

  • Partition the substring $S[l, r]$ to multiple substrings such that each of the smaller substrings have the same characters. For example, the string maakkkki is partitioned to $4$ smaller substrings, which are m, aa, kkkk, and i.

  • The density is estimated to be the sum of squares of the lengths of these partitioned substrings. Following the previous example, the estimated density would be $1^2+2^2+4^2+1^2=22$.

As the beloved Sensei of Kivotos students, you decide to help Veritas to do operations on the string $S$. Given the initial state of $S$, you have to process $Q$ queries in either of the following form:

  • 1 i c: Change the $i^{th}$ character of $S$ to $c$.

  • 2 l r: Report the projected density of $S[l, r]$.


$1 \leq N, Q \leq 2 \times 10^5$
$S$ is a string consisting of lowercase alphabets at all times
$1 \le l \le r \le N$
$1 \le i \le N$


The first line contains a two space-separated integers $N$ and $Q$, representing the length of the string $S$ and the number of queries respectively
The second line contains a string of $N$ characters representing $S$
$Q$ lines follows, the $i^{th}$ line contains 3 space-separated integers which represents the query type to be processed.


For every query of the second type, print a single integer representing the projected density of the queried substring.

Sample Input 1 Sample Output 1
9 3
2 1 9
1 7 c
2 2 8

Please log in to submit a solution to this problem

Log in