# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

This task is very simple. You are given a binary string (i.e. a string consisting of digits ‘0’ and ‘1’) of length n. The digits are numbered from the left to the right starting with 1. Now you have to execute m queries of two types on this string of the following form:

• **toggle l r**: “toggle” digits (i.e. replace them with their opposite) at all positions with indexes from l to r (1≤l≤r≤n), inclusive : each digit 0 is replaced with 1 and each digit 1 is replaced with 0.

• **print** : find and print the length of the longest non-decreasing subsequence of string s.

Subsequence of string s is a string that can be obtained from s by removing zero or more of its elements. A string is called non-decreasing if each successive digit is not less than the previous one.

The first line contains two integers **n** and **m** (**1≤n≤1000000, 1≤m≤300000**) — the length of the string s and number of queries correspondingly. The second line contains the binary string s. Next m lines contain queries in the form described in the statement.

For each query **print** output an answer on a single line.

Input | Output |
---|---|

3 5 101 print toggle 1 1 print toggle 1 3 print | 2 3 2 |

55% Solution Ratio

moiddaEarliest,

YouKnowWhoFastest, 0.1s

curly_bracesLightest, 2.4 MB

NirjhorShortest, 1604B

Login to submit