Y. Sneetches and Speeches 1 Algorithms Thread Treaps Contest
The only difference between this problem and the other two is that this problem ONLY HAS QUERIES OF TYPE 1!
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?
CONTEST LINK : http://codeforces.com/gym/102787/problem/Y
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. Queries of type 2 will not appear in this problem.
3. Queries of type 3 will not appear either.
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.
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 always 1 [for this problem] representing the query type as described in the statement, and 1≤l≤r≤n.
Print q lines, each with a single integer: the length of the longest run of sneetches with the same belly type after each query.
1 1 3
1 2 7
1 2 4
1 5 6
1 5 5
1 1 8
1 4 5
1 6 8
1 3 7
1 1 7
1 1 4
1 2 6
1 1 6
1 1 2
1 2 7
This problem was inspired by the problem Sneetches, originally written by Matt Fontaine. The original problem only had queries of type 1, and is essentially the same as this easiest version.