C. Letter Array

Codeforces

IDCF10048C

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

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: 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 ≤ 105). 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 105 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]). ## Input 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 ≤ 105). 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 105 in the whole input file. ## Output 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]). [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ S_k \in \{A, B, \dots, Z\}^* $ be a string of uppercase letters. - Let $ q_k \in \mathbb{Z}_{\geq 0} $ be the number of queries. - Each query is of type: - **Sort**: $ \texttt{"s l r"} $ — sort the substring $ S_k[l:r] $ (inclusive) in non-decreasing order. - **Get**: $ \texttt{"g l r"} $ — compute the frequency vector of letters A–Z in substring $ S_k[l:r] $. **Constraints** 1. $ 1 \leq T \leq 5 $ 2. For each test case $ k $: - $ 1 \leq |S_k| \leq 10^5 $ - $ 0 \leq q_k \leq 6000 $ 3. The sum of $ (r - l + 1) $ over all **Sort** queries across all test cases $ \leq 10^5 $ **Objective** For each test case $ k $: - Output: `"Case #k:"` - For each **Get** query $ \texttt{"g l r"} $, output a 26-tuple $ (f_A, f_B, \dots, f_Z) $, where $ f_X $ is the number of occurrences of letter $ X \in \{A, \dots, Z\} $ in $ S_k[l:r] $.

API Response (JSON)

{
  "problem": {
    "name": "C. Letter Array",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10048C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ S_k \\in \\{A, B, \\dots, Z\\}^* $ be a string of uppercase letters.  \n- L...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments