The Gellar Siblings
All submissions for this problem are available.
Monica Gellar loves to organize things. At the same time Monica has her own picky tastes and would like to include her favorite numbers 4 and 7 in her organizing / numbering system, i.e. her numbering system will consist a sequence of the numbers 4 and 7.
Monica brought home a book collection s with n books. The numberings of her book collection only consists of her favorite numbers. The digits are numbered from the left to the right starting with 1. Her brother Ross the Phd, challenges Monica to do the following steps to her numbering system. Now Monica should execute m queries of the following form:
• switch l r — Exchanges her favorite numbers at all positions with the opposite favorite number with indexes from l to r, inclusive: each digit 4 is replaced with 7 and each digit 7 is replaced with 4 (1 ≤ l ≤ r ≤ n);
Ross loves to irritate Monica being her brother and then asks to find out the following from the revised numberings she created above.
• count — find and print on the screen the length of the longest non-decreasing subsequence of books of book collection s.
Subsequence of a book collection s is a book collection that can be obtained from s by removing zero or more of its elements. A book collection s is called non-decreasing if each successive book has a numbering which is not less than the previous one according to the revised numberings.
Help Monica complete Ross’ challenge.
The first line contains two integers n and m — the size of the book collection s and the number of queries correspondingly. The second line contains n favorite digits without spaces — Monica’s initial string. Next m lines contain queries in the form described in the statement given by Ross.
For each query count print an answer on a single line.
Should contain all the constraints on the input data that you may have. Format it like:
- 1 ≤ n ≤ 10^6
- 1 ≤ m ≤ 3*10^5
Input: 2 3 47 count switch 1 2 count 3 5 747 count switch 1 1 count switch 1 3 count Output: 2 1 2 3 2
|Time Limit:||0.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions