﻿ Fuzhou University OnlineJudge ﻿
Problem 1916 Harmonious Substring Function

## Problem Description

A substring of a string T=t1…tn is a string T’=t1+i…tm+i, where 0≤i and m+i≤n. A substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix. For a string S, we define H(S) as harmonious substring function and the value of H(S) is the number of different substrings of S.

For example, the string “aab” only has five different substrings: “a”, “b”, “aa”, “ab”, “aab”, so the value of H(“aab”) is 5. Now given n empty string s0,s1,…,sn-1. Your task is to simulate the following two kinds of operations:

 I i c: Push the character c in the front of the i-th string si (0 ≤ i < n, c is a lowercase letter);

 S i j: Output the sum of the harmonious substring function from the i-th string si to the j-th string sj (inclusive) (0 ≤ i ≤ j < n), that is

## Input

The first line of the input contains an integer T (T <= 20), indicating the number of cases. Each case begins with a line containing two integers n and q (1≤n≤50,000, 1≤q≤50,000), the number of strings and the number of operations. Each of the following q lines contains an operation that is said above.

## Output

For each test case, print a line containing the test case number (beginning with 1) on its own line, then the answer, one on each line. The output is generated by the operation “S i j”.

## Sample Input

2 2 6 I 0 a S 0 1 I 1 b I 1 a I 1 a S 0 1 50000 1 S 0 50000

## Sample Output

Case 1: 1 6 Case 2: 0

## Source

2010年全国大学生程序设计邀请赛（福州）

Submit  Back  Status  Discuss
﻿