401483: GYM100482 C Letter Array

Jonas is reading the book called “Algorithms and Data Structures (for extremely experienced computer scientists edition)”. He learned a new data structure - the array of lowercase letters. As Jonas is innovative and you are his good friend, he assigned you the task to implement and to use the array of uppercase letters. This data structure is mainly a string with only uppercase letters which can operate two types of queries:

• “s l r” - sorts letters in the interval [l;r] (0 ≤ l ≤ r <  length of string);
• “g l r” - prints frequences of all letters from A to Z in the interval [l;r].

The first line contains the number of test cases T (T ≤ 5). The first line of each test case contains the string of only uppercase letters (1 ≤ thelength ≤ 10⁵). The second line of each test case contains the number of queries q (0 ≤ q ≤ 6000). The following q lines contain “s l r” or “g l r” (quotes for clarity only).

Note: the sum of all r - l in the queries of “Sort” won’t exceed 10⁵ in the whole input file.

For each test case output one line containing “Case #tc:”, where tc is the number of the test case (starting from 1). Then for each query “g l r” output a line containing 26 numbers (frequences of letters from A to Z in the given subinterval [l;r]).

1
BCA
11
g 0 0
g 1 1
g 2 2
s 1 2
g 1 1
g 2 2
s 0 2
g 1 2
g 0 0
g 1 1
g 2 2

Case #1:
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0