Find the number of different numbers in the array after applying the given operation q times | Python3 implementation for above approach ; To store the tree in lazy propagation ; To store the different numbers ; Function to update in the range [ x , y ) with given value ; check out of bound ; check for complete overlap ; find the mid number ; check for pending updates ; make lazy [ id ] = 0 , so that it has no pending updates ; call for two child nodes ; Function to find non - zero integersin the range [ l , r ) ; if id contains positive number ; There is no need to see the children , because all the interval have same number ; check for out of bound ; find the middle number ; call for two child nodes ; Driver code ; size of the array and number of queries ; Update operation for l , r , x , id , 0 , n ; Query operation to get answer in the range [ 0 , n - 1 ] ; Print the count of non - zero elements
N = 100005 NEW_LINE lazy = [ 0 ] * ( 4 * N ) ; NEW_LINE se = set ( ) NEW_LINE def update ( x , y , value , id , l , r ) : NEW_LINE INDENT if ( x >= r or l >= y ) : NEW_LINE INDENT return ; NEW_LINE DEDENT if ( x <= l and r <= y ) : NEW_LINE INDENT lazy [ id ] = value ; NEW_LINE return ; NEW_LINE DEDENT mid = ( l + r ) // 2 ; NEW_LINE if ( lazy [ id ] ) : NEW_LINE INDENT lazy [ 2 * id ] = lazy [ 2 * id + 1 ] = lazy [ id ] ; NEW_LINE DEDENT lazy [ id ] = 0 ; NEW_LINE update ( x , y , value , 2 * id , l , mid ) ; NEW_LINE update ( x , y , value , 2 * id + 1 , mid , r ) ; NEW_LINE DEDENT def query ( id , l , r ) : NEW_LINE INDENT if ( lazy [ id ] ) : NEW_LINE INDENT se . add ( lazy [ id ] ) ; NEW_LINE return ; NEW_LINE DEDENT if ( r - l < 2 ) : NEW_LINE INDENT return ; NEW_LINE DEDENT mid = ( l + r ) // 2 ; NEW_LINE query ( 2 * id , l , mid ) ; NEW_LINE query ( 2 * id + 1 , mid , r ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 ; q = 3 ; NEW_LINE update ( 1 , 4 , 1 , 1 , 0 , n ) ; NEW_LINE update ( 0 , 2 , 2 , 1 , 0 , n ) ; NEW_LINE update ( 3 , 4 , 3 , 1 , 0 , n ) ; NEW_LINE query ( 1 , 0 , n ) ; NEW_LINE print ( len ( se ) ) ; NEW_LINE DEDENT