G. Polycarp and Palindromes

Codeforces

IDCF10083G

Time2000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Polycarp has got the string S, which consists of N small Latin letters. Polycarp is eager to know if the given substrings of the string S are palindromes. A palindrome is a string which is read identically right to left and left to right. But it is not enough for Polycarp: he can change the signs in the string. Polycarp is eager to know if it is possible to know and define very quickly if the substring of the string S is a palindrome if the letters in S can be substituted. Polycarp conducts K operations one after another. There is string S in the first line. Its length is N, 1 ≤ N ≤ 100000. S consists of only small Latin letters. The second line contains the only integer K, 1 ≤ K ≤ 100000 — the number of operations. Next K lines contain the descriptions of operations, one in each line. Each line starts with the integer ti, which can take the values 1 and 2. If ti equals 1, two integers li and ri, 1 ≤ li ≤ ri ≤ N follow it. It means — it is necessary to define if the substring slisli + 1... sri is a palindrome. If ti equals 2, it is followed by the integer pi and a small Latin letter ci. It means — to substitute in the string S sign in position pi to ci Output "YES" in separate lines for each operation of the palindrome definition if the substring is a palindrome, or "NO", if it isn’t (without quotations). ## Input There is string S in the first line. Its length is N, 1 ≤ N ≤ 100000. S consists of only small Latin letters.The second line contains the only integer K, 1 ≤ K ≤ 100000 — the number of operations.Next K lines contain the descriptions of operations, one in each line. Each line starts with the integer ti, which can take the values 1 and 2. If ti equals 1, two integers li and ri, 1 ≤ li ≤ ri ≤ N follow it. It means — it is necessary to define if the substring slisli + 1... sri is a palindrome. If ti equals 2, it is followed by the integer pi and a small Latin letter ci. It means — to substitute in the string S sign in position pi to ci ## Output Output "YES" in separate lines for each operation of the palindrome definition if the substring is a palindrome, or "NO", if it isn’t (without quotations). [samples]

**Definitions** Let $ S \in \Sigma^N $ be a string of length $ N $, where $ \Sigma $ is the set of lowercase Latin letters. Let $ K \in \mathbb{Z}^+ $ be the number of operations. **Operations** For each operation $ i \in \{1, \dots, K\} $: - If $ t_i = 1 $: given $ l_i, r_i \in \mathbb{Z} $ with $ 1 \leq l_i \leq r_i \leq N $, query whether the substring $ S[l_i:r_i] $ is a palindrome. - If $ t_i = 2 $: given $ p_i \in \mathbb{Z} $ with $ 1 \leq p_i \leq N $ and $ c_i \in \Sigma $, update $ S[p_i] \leftarrow c_i $. **Constraints** 1. $ 1 \leq N \leq 10^5 $ 2. $ 1 \leq K \leq 10^5 $ 3. For all operations: - $ t_i \in \{1, 2\} $ - If $ t_i = 1 $: $ 1 \leq l_i \leq r_i \leq N $ - If $ t_i = 2 $: $ 1 \leq p_i \leq N $, $ c_i \in \Sigma $ **Objective** For each operation with $ t_i = 1 $, output: $$ \begin{cases} \text{``YES''} & \text{if } S[l_i:r_i] = \text{reverse}(S[l_i:r_i]) \\ \text{``NO''} & \text{otherwise} \end{cases} $$

API Response (JSON)

{
  "problem": {
    "name": "G. Polycarp and Palindromes",
    "description": {
      "content": "Polycarp has got the string S, which consists of N small Latin letters. Polycarp is eager to know if the given substrings of the string S are palindromes. A palindrome is a string which is read identi",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10083G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp has got the string S, which consists of N small Latin letters. Polycarp is eager to know if the given substrings of the string S are palindromes. A palindrome is a string which is read identi...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S \\in \\Sigma^N $ be a string of length $ N $, where $ \\Sigma $ is the set of lowercase Latin letters.  \nLet $ K \\in \\mathbb{Z}^+ $ be the number of operations.  \n\n**Operations*...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments