Randomness

You’re given a string S of N characters. It’s known that the string consists of lowercase latin letters. The string is generated randomly. That means that every symbol is chosen randomly and independently from others from the set {‘a’, ‘b’, …, ‘z’}. All the letters has equal probability to appear.

You’re given Q queries on this string. Each query is of the form P C, where P is an integer between 1 and N (both inclusive) and C is a character from the set {‘a’, ‘b’, …, ‘z’}. Both P and C were chosen at random and independently from other queries.

When you have a query of the form P C you have to change the Pth symbol of S to C. After every change we ask you to output the number of distinct nonempty sub-strings of S.

Input Format
The first line of input consists of two single space separated integers N and Q - the length of the string S and the number of queries respectively.

The second line contains the string S itself.

The following Q lines describe the queries in the form P C, where P and C are also separated with a single space.

Constraints

4 ≤ N ≤ 75000
4 ≤ Q ≤ 75000

Output Format
Output Q lines. Output the number of distinct substrings of S after the ith query on theith line of the output.

Sample Input

4 4 
aaab
1 a
2 b
3 c
4 d

Sample Output

7
7
9
10

Explanation

after replacing the character at 1st index with a, we still have the original string aaab. The total non empty substrings of aaab are

a b aa ab aaa aab aaab

hence 7.

after replacing the character at 2nd index with b, we have the string abab. The total non empty substrings of abab are

a b ab ba aba bab abab

hence 7.

after replacing the character at 3rd index with c, we have the string abcb. The total non empty substrings of abcb are

a b c ab bc cb abc bcb abcb

hence 9.

after replacing the character at 4th index with d, we have the string abcd. The total non empty substrings of abcd are

a b c d ab bc cd abc bcd abcd

hence 10.

Scoring

There are 12 test cases.

The first four test cases N = 100 and Q = 500
The next four test cases N = 75000 and Q = 10
The last four test cases N = 75000 and Q = 75000

solution-->

The solution consists of constructing the suffix array and then finding the number of distinct substrings based on the Longest Common Prefixes.

One key observation here is that:

If you look through the prefixes of each suffix of a string, you have covered all substrings of that string.

Let us take an example: BANANA

Suffixes are:

0) BANANA
1) ANANA
2) NANA
3) ANA
4) NA
5) A

It would be a lot easier to go through the prefixes if we sort the above set of suffixes, as we can skip the repeated prefixes easily.

Sorted set of suffixes:

5) A
3) ANA
1) ANANA
0) BANANA
4) NA
2) NANA

From now on, 

LCP = Longest Common Prefix of 2 strings.

Initialize

ans = length(first suffix) = length("A") = 1.

Now consider the consecutive pairs of suffixes, i.e, [A, ANA], [ANA, ANANA], [ANANA, BANANA], etc. from the above set of sorted suffixes.

We can see that,

LCP("A", "ANA") = "A".

All characters that are not part of the common prefix contribute to a distinct substring. In the above case, they are 'N' and 'A'. So they should be added to ans.

So we have, 

1 2	ans += length("ANA") - LCP("A", "ANA") ans = ans + 3 - 1 = ans + 2 = 3

Do the same for the next pair of consecutive suffixes: ["ANA", "ANANA"]

1 2 3 4

LCP("ANA", "ANANA") = "ANA". ans += length("ANANA") - length(LCP) => ans = ans + 5 - 3 => ans = 3 + 2 = 5.

Similarly, we have:

1 2	LCP("ANANA", "BANANA") = 0 ans = ans + length("BANANA") - 0 = 11

1 2	LCP("BANANA", "NA") = 0 ans = ans + length("NA") - 0 = 13

1 2	LCP("NA", "NANA") = 2 ans = ans + length("NANA") - 2 = 15

Hence the number of distinct substrings for the string "BANANA" = 15.

code---->

#include<iostream>

#include<string>

#include<algorithm>

using namespace std ;

int LCP(string s , string s1){

int x=s.size();

int y=s1.size();

if(x>y)

    x=y;

    int count=0 ;

    for(int i=0 ; i < x ;i++){

        if(s.at(i)==s1.at(i))

            count++;

        else

         break ;

    }

return count ;

}

void check(string s){

    int x= s.size();

    string ss[x];

    

    for(int i=0 ; i<x ;i++)

        ss[i]= s.substr(i);     

         sort(ss,ss+x);

         int ans=0;

         ans=ss[0].size();

      for(int i=1 ; i<x ; i++)

    ans+=( ss[i].size() - LCP(ss[i],ss[i-1]));

    cout << ans << endl ;    

}

int main(){

    int x=0,y=0 ;   

    cin >> x >> y ;

     string s ;

    cin >> s ;

    while(y--){

          int p ;

          char z ;

         cin >>p >> z ;

         s[p-1]=z;

         check(s);

     }

    return 0 ;   

}