Visit Them All

 You are given a binary string 

S$S$ of length N$N$.

Let G$G$ be a complete directed graph of N$N$ vertices numbered from 1$1$ to N$N$. There is a directed edge going from vertex u$u$ to v$v$ if one of the following is true:

• Su=Sv$S_u=S_v$ and u<v$u<v$
• Su≠Sv$S_u\ne S_v$ and u>v$u>v$

For example, if S=1010$S=1010$ then G$G$ looks like this:

You will be given Q$Q$ queries of two different types:

• 1$1$ L$L$ R$R$ - Flip all the bits in S$S$ in range [L,R]$[L,R]$ and update G$G$ accordingly.
• 2$2$ L$L$ R$R$ X$X$ - Find whether there is a path that starts from vertex X$X$ and visits each vertex in G[L,R]$G[L,R]$ exactly once (a hamiltonian path in other words).

G[L,R]$G[L,R]$ is the subgraph induced by the vertices in the range [L,R]$[L,R]$ and the edges connecting them. For example, if S=1010$S=1010$ then G[2,4]$G[2,4]$ consists of the vertices 2$2$, 3$3$, and 4$4$, and the three edges 2→4$2\to 4$, 4→3$4\to 3$, and 3→2$3\to 2$.

Input Format

• The first line contains two integers, N$N$ and Q$Q$.
• The second line contains a binary string S$S$ of length N$N$.
• The ith$i^{th}$ line of the next Q$Q$ lines contains the description of the ith$i^{th}$ query.

Output Format

For each query of type 2$2$, print a single line containing YES if there's a hamiltonian path starting from vertex X$X$, or NO otherwise.

You may print each character of the string in uppercase or lowercase (for example, the strings yEs, yes, Yes and YES will all be treated as identical).

Constraints

• 1≤N,Q≤5⋅105$1\le N,Q\le 5\cdot {10}^5$
• For queries of type 1$1$, 1≤L≤R≤N$1\le L\le R\le N$
• For queries of type 2$2$, 1≤L≤X≤R≤N$1\le L\le X\le R\le N$

Subtasks

• Subtask #1 (100 points): original constraints

Sample Input 1 

5 7
11011
2 1 5 3
2 3 5 3
2 3 5 4
1 4 5
2 1 5 2
1 2 3
2 3 5 4

Sample Output 1 

YES
NO
YES
NO
YES

Explanation

Here's what G$G$ initially looks like:

• First query: 3→1→2→4→5$3\to 1\to 2\to 4\to 5$ is a possible hamiltonian path.
• Second query: There's no hamiltonian path that visits the vertices 3$3$, 4$4$, and 5$5$ which starts from 3$3$.
• Third query: 4→5→3$4\to 5\to 3$ is a possible hamiltonian path.
• Fourth query: Flip the bits in the range [4,5]$[4,5]$ so S$S$ becomes equal to 11000$11000$.
• Fifth query: There's no hamiltonian path that visits the vertices 1$1$, 2$2$, 3$3$, 4$4$, and 5$5$ which starts from 2$2$.
• Sixth query: Flip the bits in the range [2,3]$[2,3]$ so S$S$ becomes equal to 10100$10100$.
• Seventh query: 4→5→3$4\to 5\to 3$ is a possible hamiltonian path.

• Tweet
• Share
• Share
• Share
• Share

Related Post