Array range queries for searching an element | Structure to represent a query range ; Find the root of the group containing the element at index x ; merge the two groups containing elements at indices x and y into one group ; make n subsets with every element as its root ; consecutive elements equal in value are merged into one single group ; Driver Code ; check if the current element in consideration is equal to x or not if it is equal , then x exists in the range ; Print if x exists or not
class Query : NEW_LINE INDENT def __init__ ( self , L , R , X ) : NEW_LINE INDENT self . L = L NEW_LINE self . R = R NEW_LINE self . X = X NEW_LINE DEDENT DEDENT maxn = 100 NEW_LINE root = [ 0 ] * maxn NEW_LINE def find ( x ) : NEW_LINE INDENT if x == root [ x ] : NEW_LINE INDENT return x NEW_LINE DEDENT else : NEW_LINE INDENT root [ x ] = find ( root [ x ] ) NEW_LINE return root [ x ] NEW_LINE DEDENT DEDENT def uni ( x , y ) : NEW_LINE INDENT p = find ( x ) NEW_LINE q = find ( y ) NEW_LINE if p != q : NEW_LINE INDENT root [ p ] = root [ q ] NEW_LINE DEDENT DEDENT def initialize ( a , n , q , m ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT root [ i ] = i NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT if a [ i ] == a [ i - 1 ] : NEW_LINE INDENT uni ( i , i - 1 ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 1 , 1 , 5 , 4 , 5 ] NEW_LINE n = len ( a ) NEW_LINE q = [ Query ( 0 , 2 , 2 ) , Query ( 1 , 4 , 1 ) , Query ( 2 , 4 , 5 ) ] NEW_LINE m = len ( q ) NEW_LINE initialize ( a , n , q , m ) NEW_LINE for i in range ( m ) : NEW_LINE INDENT flag = False NEW_LINE l = q [ i ] . L NEW_LINE r = q [ i ] . R NEW_LINE x = q [ i ] . X NEW_LINE p = r NEW_LINE while p >= l : NEW_LINE INDENT if a [ p ] == x : NEW_LINE INDENT flag = True NEW_LINE break NEW_LINE DEDENT p = find ( p ) - 1 NEW_LINE DEDENT if flag : NEW_LINE INDENT print ( " % d ▁ exists ▁ between ▁ [ % d , ▁ % d ] " % ( x , l , r ) ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " % d ▁ does ▁ not ▁ exists ▁ between ▁ [ % d , ▁ % d ] " % ( x , l , r ) ) NEW_LINE DEDENT DEDENT DEDENT