C. Sneetches and Speeches 3 SOLUTION

C. Sneetches and Speeches 3 Algorithms Thread Treaps Contest

The sneetches are back on the beaches, with the great Sylvester McMonkey McBean! The ith sneetch has ai stars on his belly (0≤ai≤1). Just like normal, many [l…r] ranges of sneetches will go through Sylvesters xor-with-1-inator. Formally, after an operation, for all positions between l and r inclusive, the sneetch at that position will have a star on his belly after if and only if he didn’t have a star on his belly immediately before walking through the machine. You need to know the largest continuous range of sneetches that all have the same type of belly at each step. Easy stuff, right?
But wait! There is a very important detail still unaddressed: we are on a beach! And the great orator Demosthenes practices his speeches on a beach. Demosthenes is giving an inspiring speech which may at times incite the following behavior, doing one of the three things q times:
1. Do the usual operation: make the sneetches in positions [l..r] go through the machine. l≤r
2. Talk to sneetches [l..r] and convince them to reverse their order. After moving, the sneetches are relabeled 1 to n from left to right.
3. Sort the range of sneetches [l..r] by the number of stars on their bellies, in nondecreasing order.
After each operation, Sylvester needs you to report the size of the largest continuous range of sneetches that have the same number of stars on their belly.
Input
The first line will contain two integers: n and q representing the number of sneetches and the number of queries. 1≤n,q≤3∗105
The second line will contain a string of 0s and 1s of length n. The ith character represents the number of stars on the ith sneech’s belly initially.
q lines follow, each of the form t l r where t is 1, 2, or 3 representing the query type as described in the statement, and 1≤l≤r≤n.
Output
Print q lines, each with a single integer: the length of the longest run of sneetches with the same belly type after each query.
Examples
inputCopy
8 8
00000000
1 1 3
2 2 7
2 2 4
2 5 6
2 5 5
3 1 8
1 4 5
3 6 8
outputCopy
5
4
4
3
3
5
5
5
inputCopy
7 7
0111111
3 3 7
1 1 7
2 1 4
2 2 6
1 1 6
2 1 2
1 2 7
outputCopy
6
6
3
3
3
3
2
Note
This problem was inspired by the problem Sneetches, originally written by Matt Fontaine. The original problem only had queries of type 1.

Related :

Related :

Leave a Comment