Queries for number of distinct elements in a subarray | Python3 code to find number of distinct numbers in a subarray ; structure to store queries ; updating the bit array ; querying the bit array ; initialising bit array ; holds the rightmost index of any number as numbers of a [ i ] are less than or equal to 10 ^ 6 ; answer for each query ; If last visit is not - 1 update - 1 at the idx equal to last_visit [ arr [ i ] ] ; Setting last_visit [ arr [ i ] ] as i and updating the bit array accordingly ; If i is equal to r of any query store answer for that query in ans [ ] ; print answer for each query ; Driver Code
MAX = 1000001 NEW_LINE class Query : NEW_LINE INDENT def __init__ ( self , l , r , idx ) : NEW_LINE INDENT self . l = l NEW_LINE self . r = r NEW_LINE self . idx = idx NEW_LINE DEDENT DEDENT def update ( idx , val , bit , n ) : NEW_LINE INDENT while idx <= n : NEW_LINE INDENT bit [ idx ] += val NEW_LINE idx += idx & - idx NEW_LINE DEDENT DEDENT def query ( idx , bit , n ) : NEW_LINE INDENT summ = 0 NEW_LINE while idx : NEW_LINE INDENT summ += bit [ idx ] NEW_LINE idx -= idx & - idx NEW_LINE DEDENT return summ NEW_LINE DEDENT def answeringQueries ( arr , n , queries , q ) : NEW_LINE INDENT bit = [ 0 ] * ( n + 1 ) NEW_LINE last_visit = [ - 1 ] * MAX NEW_LINE ans = [ 0 ] * q NEW_LINE query_counter = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if last_visit [ arr [ i ] ] != - 1 : NEW_LINE INDENT update ( last_visit [ arr [ i ] ] + 1 , - 1 , bit , n ) NEW_LINE DEDENT last_visit [ arr [ i ] ] = i NEW_LINE update ( i + 1 , 1 , bit , n ) NEW_LINE while query_counter < q and queries [ query_counter ] . r == i : NEW_LINE INDENT ans [ queries [ query_counter ] . idx ] = query ( queries [ query_counter ] . r + 1 , bit , n ) - query ( queries [ query_counter ] . l , bit , n ) NEW_LINE query_counter += 1 NEW_LINE DEDENT DEDENT for i in range ( q ) : NEW_LINE INDENT print ( ans [ i ] ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 1 , 1 , 2 , 1 , 3 ] NEW_LINE n = len ( a ) NEW_LINE queries = [ Query ( 0 , 4 , 0 ) , Query ( 1 , 3 , 1 ) , Query ( 2 , 4 , 2 ) ] NEW_LINE q = len ( queries ) NEW_LINE queries . sort ( key = lambda x : x . r ) NEW_LINE answeringQueries ( a , n , queries , q ) NEW_LINE DEDENT