Palindrome Query

AtCoder

IDabc331_f

Time3000ms

Memory256MB

Difficulty—

You are given a string $S$ of length $N$ consisting of lowercase English letters. Process $Q$ queries described below in the order they are given. There are two types of queries: * `1 x c` : Change the $x$\-th character of $S$ to the lowercase English letter $c$. * `2 L R` : If the substring formed by the $L$\-th through $R$\-th characters of $S$ is a palindrome, print `Yes`; otherwise, print `No`. ## Constraints * $1 \leq N \leq 10^6$ * $1 \leq Q \leq 10^5$ * $S$ is a string of length $N$ consisting of lowercase English letters. * $1 \leq x \leq N$ * $c$ is a lowercase English letter. * $1 \leq L \leq R \leq N$ * $N, Q, x, L, R$ are integers. ## Input The input is given from Standard Input in the following format. Here, $\text{query}_i$ is the $i$\-th query to be processed. $N$ $Q$ $S$ $\text{query}_1$ $\text{query}_2$ $\vdots$ $\text{query}_Q$ Each query is given in one of the following formats: $1$ $x$ $c$ $2$ $L$ $R$ [samples]

Samples

Input #1

Output #1

Yes
No
Yes
No
Yes
Yes

Initially, $S =$ `abcbacb`.  
For the first query, the string formed by the $1$\-st through $5$\-th characters of $S$ is `abcba`, which is a palindrome. Thus, print `Yes`.  
For the second query, the string formed by the $4$\-th through $7$\-th character of $S$ is `bacb`, which is not a palindrome. Thus, print `No`.  
For the third query, the string formed by the $2$\-nd through $2$\-nd character of $S$ is `b`, which is a palindrome. Thus, output `Yes`.  
For the fourth query, change the $5$\-th character of $S$ to `c`. $S$ becomes `abcbccb`.  
For the fifth query, the string formed by the $1$\-st through $5$\-th character of $S$ is `abcbc`, which is not a palindrome. Thus, output `No`.  
For the sixth query, the string formed by the $4$\-th through $7$\-th character of $S$ is `bccb`, which is a palindrome. Thus, output `Yes`.  
For the seventh query, change the $4$\-th character of $S$ to `c`. $S$ becomes `abccccb`.  
For the eighth query, the string formed by the $3$\-rd through $6$\-th character of `cccc`, which is a palindrome. Thus, output `Yes`.

API Response (JSON)

{
  "problem": {
    "name": "Palindrome Query",
    "description": {
      "content": "You are given a string $S$ of length $N$ consisting of lowercase English letters.   Process $Q$ queries described below in the order they are given.   There are two types of queries: *   `1 x c` : Ch",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc331_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a string $S$ of length $N$ consisting of lowercase English letters.  \nProcess $Q$ queries described below in the order they are given.  \nThere are two types of queries:\n\n*   `1 x c` : Ch...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments