Find the number of different numbers in the array after applying the given operation q times | JavaScript 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 integers in 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 ; 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
var N = 100005 ; var lazy = Array ( 4 * N ) . fill ( 0 ) ; var se = new Set ( ) ; function update ( x , y , value , id , l , r ) { if ( x >= r l >= y ) return ; if ( x <= l && r <= y ) { lazy [ id ] = value ; return ; } var mid = parseInt ( ( l + r ) / 2 ) ; if ( lazy [ id ] != 0 ) lazy [ 2 * id ] = lazy [ 2 * id + 1 ] = lazy [ id ] ; lazy [ id ] = 0 ; update ( x , y , value , 2 * id , l , mid ) ; update ( x , y , value , 2 * id + 1 , mid , r ) ; } function query ( id , l , r ) { if ( lazy [ id ] != 0 ) { se . add ( lazy [ id ] ) ; return ; } if ( r - l < 2 ) return ; var mid = parseInt ( ( l + r ) / 2 ) ; query ( 2 * id , l , mid ) ; query ( 2 * id + 1 , mid , r ) ; } var n = 5 , q = 3 ; update ( 1 , 4 , 1 , 1 , 0 , n ) ; update ( 0 , 2 , 2 , 1 , 0 , n ) ; update ( 3 , 4 , 3 , 1 , 0 , n ) ; query ( 1 , 0 , n ) ; document . write ( se . size ) ;