human
Find the count of distinct numbers in a range | Function to perform queries in a range.
No overlap.
Totally Overlap.
Partial Overlap.
Finding the Answer for the left Child.
Finding the Answer for the right Child.
Combining the BitMasks.
Function to perform update operation in the Segment seg.
Forming the BitMask.
Updating the left Child.
Updating the right Child.
Updating the BitMask.
Building the Segment Tree.
Building the Initial BitMask.
Building the left seg tree.
Building the right seg tree.
Forming the BitMask.
Utility Function to answer the queries.
Counting the set bits which denote the distinct elements.
Updating the value.
Driver Code"
Solution in Python:
assistant
#Here is code to find the count of distinct numbers in a range and the other steps required.
 def query ( start , end , left , right , node , seg ) :
	if ( end < left or start > right ) :
		return 0
	elif ( start >= left and end <= right ) :
		return seg [ node ]
	else :
		mid = ( start + end ) // 2
		leftChild = query ( start , mid , left , right , 2 * node , seg )
		rightChild = query ( mid + 1 , end , left , right , 2 * node + 1 , seg )
		return ( leftChild rightChild )
def update ( left , right , index , Value , node , ar , seg ) :
	if ( left == right ) :
		ar [ index ] = Value
		seg [ node ] = ( 1 << Value )
		return
	mid = ( left + right ) // 2
	if ( index > mid ) :
		update ( mid + 1 , right , index , Value , 2 * node + 1 , ar , seg )
	else :
		update ( left , mid , index , Value , 2 * node , ar , seg )
	seg [ node ] = ( seg [ 2 * node ] seg [ 2 * node + 1 ] )
def build ( left , right , node , ar , eg ) :
	if ( left == right ) :
		seg [ node ] = ( 1 << ar [ left ] )
		return
	mid = ( left + right ) // 2
	build ( left , mid , 2 * node , ar , seg )
	build ( mid + 1 , right , 2 * node + 1 , ar , seg )
	seg [ node ] = ( seg [ 2 * node ] seg [ 2 * node + 1 ] )
def getDistinctCount ( queries , ar , seg , n ) :
	for i in range ( len ( queries ) ) :
		op = queries [ i ] [ 0 ]
		if ( op == 2 ) :
			l = queries [ i ] [ 1 ]
			r = queries [ i ] [ 2 ]
			tempMask = query ( 0 , n - 1 , l - 1 , r - 1 , 1 , seg )
			countOfBits = 0
			for i in range ( 63 , - 1 , - 1 ) :
				if ( tempMask & ( 1 << i ) ) :
					countOfBits += 1
			print ( countOfBits )
		else :
			index = queries [ i ] [ 1 ]
			val = queries [ i ] [ 2 ]
			update ( 0 , n - 1 , index - 1 , val , 1 , ar , seg )
if __name__ == ' _ _ main _ _ ' :
	n = 7
	ar = [ 1 , 2 , 1 , 3 , 1 , 2 , 1 ]
	seg = [ 0 ] * 4 * n
	build ( 0 , n - 1 , 1 , ar , seg )
	q = 5
	queries = [ [ 2 , 1 , 4 ] , [ 1 , 4 , 2 ] , [ 1 , 5 , 2 ] , [ 2 , 4 , 6 ] , [ 2 , 1 , 7 ] ]
	getDistinctCount ( queries , ar , seg , n )