Query to find length of the longest subarray consisting only of 1 s | Python 3 Program for the above approach ; Arrays to store prefix sums , suffix and MAX 's node respectively ; Function to construct Segment Tree ; MAX array for node MAX ; Array for prefix sum node ; Array for suffix sum node ; Calculate MAX node ; Function to update Segment Tree ; Update at position ; Update sums from bottom to the top of Segment Tree ; Update MAX tree ; Update pref tree ; Update suf tree ; Function to perform given queries ; Stores count of queries ; Traverse each query ; Print longest length of subarray in [ 1 , N ] ; Flip the character ; Driver Code ; Size of array ; Given array ; Given queries ; Number of queries
INF = 1000000 NEW_LINE pref = [ 0 for i in range ( 500005 ) ] NEW_LINE suf = [ 0 for i in range ( 500005 ) ] NEW_LINE MAX = [ 0 for i in range ( 500005 ) ] NEW_LINE def build ( a , tl , tr , v ) : NEW_LINE INDENT global MAX NEW_LINE global pref NEW_LINE global suf NEW_LINE if ( tl == tr ) : NEW_LINE INDENT MAX [ v ] = a [ tl ] NEW_LINE pref [ v ] = a [ tl ] NEW_LINE suf [ v ] = a [ tl ] NEW_LINE DEDENT else : NEW_LINE INDENT tm = ( tl + tr ) // 2 NEW_LINE build ( a , tl , tm , v * 2 ) NEW_LINE build ( a , tm + 1 , tr , v * 2 + 1 ) NEW_LINE MAX [ v ] = max ( MAX [ v * 2 ] , max ( MAX [ v * 2 + 1 ] , suf [ v * 2 ] + pref [ v * 2 + 1 ] ) ) NEW_LINE pref [ v ] = max ( pref [ v * 2 ] , pref [ 2 * v ] + ( pref [ 2 * v ] == tm - tl + 1 ) * pref [ v * 2 + 1 ] ) NEW_LINE suf [ v ] = max ( suf [ v * 2 + 1 ] , suf [ 2 * v + 1 ] + suf [ v * 2 ] * ( suf [ 2 * v + 1 ] == tr - tm ) ) NEW_LINE DEDENT DEDENT def update ( a , pos , tl , tr , v ) : NEW_LINE INDENT global pref NEW_LINE global suf NEW_LINE global MAX NEW_LINE if ( tl > pos or tr < pos ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( tl == tr and tl == pos ) : NEW_LINE INDENT MAX [ v ] = a [ pos ] NEW_LINE pref [ v ] = a [ pos ] NEW_LINE suf [ v ] = a [ pos ] NEW_LINE DEDENT else : NEW_LINE INDENT tm = ( tl + tr ) // 2 NEW_LINE update ( a , pos , tl , tm , v * 2 ) NEW_LINE update ( a , pos , tm + 1 , tr , v * 2 + 1 ) NEW_LINE MAX [ v ] = max ( MAX [ v * 2 ] , max ( MAX [ v * 2 + 1 ] , suf [ v * 2 ] + pref [ v * 2 + 1 ] ) ) NEW_LINE pref [ v ] = max ( pref [ v * 2 ] , pref [ 2 * v ] + ( pref [ 2 * v ] == tm - tl + 1 ) * pref [ v * 2 + 1 ] ) NEW_LINE suf [ v ] = max ( suf [ v * 2 + 1 ] , suf [ 2 * v + 1 ] + ( suf [ 2 * v + 1 ] == tr - tm ) * suf [ v * 2 ] ) NEW_LINE DEDENT DEDENT def solveQueries ( arr , n , Q , k ) : NEW_LINE INDENT global MAX NEW_LINE cntQuery = len ( Q ) NEW_LINE build ( arr , 0 , n - 1 , 1 ) NEW_LINE for i in range ( cntQuery ) : NEW_LINE INDENT if ( Q [ i ] [ 0 ] == 1 ) : NEW_LINE INDENT print ( MAX [ 1 ] , end = " ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT arr [ Q [ i ] [ 1 ] - 1 ] ^= 1 NEW_LINE update ( arr , Q [ i ] [ 1 ] - 1 , 0 , n - 1 , 1 ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 10 NEW_LINE arr = [ 1 , 1 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 1 ] NEW_LINE Q = [ [ 1 ] , [ 2 , 3 ] , [ 1 ] ] NEW_LINE K = 3 NEW_LINE solveQueries ( arr , N , Q , K ) NEW_LINE DEDENT