Flip and Combos
Time limit2sMemory limit512 MB
Maintain a binary array under range flip operations and answer queries for the longest run of equal bits inside a subarray.
- Level
Hard8 of 10
- Topics
- Segment tree, Divide and conquer, Array, Linked list
- Solved
- No attempts yet
Problem
A binary array is an array whose elements are each 0 or 1. Aleka has a binary array B of length N. The elements of B are indexed from 1 to N.
Aleka will play with her array. She runs Q queries one after another. Each query is one of the following types:
FLIPL R: Flip every bit of B from index L to R, inclusive. Flipping a bit means changing its value from 0 to 1, or from 1 to 0.COMBOL R: Let B' be the subarray of B containing only the bits indexed between L and R, inclusive. Find the length of the longest contiguous subarray of B' in which all elements have the same value.
Every query is executed in input order, and for each COMBO query you output the answer to that query.
Input
The first line contains two integers N Q (1 ≤ N, Q ≤ 100,000), the length of the array and the number of queries. The second line contains a string of N characters ('0' or '1') representing the binary array B. The i-th character of the string corresponds to the i-th element of B ('0' represents 0 and '1' represents 1). The next Q lines each contain three integers T L R (1 ≤ T ≤ 2; 1 ≤ L ≤ R ≤ N) describing a query. If T = 1 the query is a FLIP query; otherwise it is a COMBO query.
Output
For each COMBO query, print the answer to that query in the order the queries are executed.