Is Palindrome?

★★★★★

4.8

8 votes

String, Lazy Propagation in Interval/Segment Trees, Data Structures, Advanced Data Structures

Details

Submissions

Discussion

Editorial

Problem

Suppose you are given a string $s$ of size $n$ consisting of lowercase letters only. You will be given $q$ queries. Each query can be of below two types:

$1$ $l$ $r$ $ch:$ From $l$ to $r$ , change characters in the string $s$ to $ch$ , i.e., make $s[l] = s[l + 1] =$ $...$ $s[r] = ch$
$2$ $l$ $r:$ Suppose string $t$ is the substring of string $s$ from index $l$ to $r$ , or, $t =$ $s[l ... r]$

For each query of type $2$ answer will be Yes, if we can rearrange the characters in the string $t$ so that the string becomes a palindrome. Otherwise, the answer is No.

Do note that query $1$ makes permanent changes to the string $s$ , i.e., for all queries after it, the string is modified.

For each query of type $2$ , you don't make changes to the string $s$ . Or in other words, the string remains the same after query of type $2$ .

It is recommended to use Fast I/O.

Input Format

The first line contains a string $s$ of size $n$ .
The second line contains one integer $q$ - number of queries. Then $q$ queries follow.
Each query will be of one of the two types as explained above.

Output Format

For each query of type $2$ , output the answer in a separate line.

Constraints

$1 \leq n \leq 10^{5}$
$1 \leq q \leq 10^5$
In each query, $1 \leq l \leq r \leq n$ will always follow.
In each query of type $1$ , $a \leq ch \leq z$ will always follow.
The string $s$ consists of lowercase letters only.
It is guaranteed that there will be at least $1$ query of type $2$ .

Time Limit: 2.5

Memory Limit: 256

Source Limit:

Explanation

The given string is $abcsjakj$ .

After the first query, the string becomes $abczzzzj$ .
The second query considers the substring $s[6..8] = zzj$ . Let's say this is denoted by $t$ . In this string, characters can be rearranged such that $t$ becomes $zjz$ , which is a palindrome. Therefore the answer to this query is $Yes$ .
After the third query, the string becomes $aaaaazzj$ .
After the fourth query, the string becomes $aaffazzj$ .
The fifth query considers the substring $s[3...6] = ffaz$ . It can be shown that, this substring can't be converted into a palindrome. Therefore the answer to this query is $No$ .
The sixth query considers the substring $s[3...7] = ffazz$ . Let's say this is denoted by $t$ . We can see that the string $t$ is a palindrome. Therefore the answer to this query is $Yes$ .
The seventh query considers the substring $s[1...1] = a$ . A string of size 1 is always a palindrome. Therefore the answer to this query is $Yes$ .