Find the numbers of strings that can be formed after processing Q queries | Python3 program to implement above approach ; To store the size of string and number of queries ; To store parent and rank of ith place ; To store maximum interval ; Function for initialization ; Function to find parent ; Function to make union ; Power function to calculate a raised to m1 under modulo 10000007 ; Function to take maxmium interval ; Function to find different possible strings ; make union of all chracters which are meant to be same ; find number of different sets formed ; return the required answer ; Driver Code ; queries
N = 2005 NEW_LINE mod = 10 ** 9 + 7 NEW_LINE n , q = 0 , 0 NEW_LINE par = [ 0 for i in range ( N ) ] NEW_LINE Rank = [ 0 for i in range ( N ) ] NEW_LINE m = dict ( ) NEW_LINE def initialize ( ) : NEW_LINE INDENT for i in range ( n + 1 ) : NEW_LINE INDENT Rank [ i ] , par [ i ] = 0 , i NEW_LINE DEDENT DEDENT def find ( x ) : NEW_LINE INDENT if ( par [ x ] != x ) : NEW_LINE INDENT par [ x ] = find ( par [ x ] ) NEW_LINE DEDENT return par [ x ] NEW_LINE DEDENT def Union ( x , y ) : NEW_LINE INDENT xpar = find ( x ) NEW_LINE ypar = find ( y ) NEW_LINE if ( Rank [ xpar ] < Rank [ ypar ] ) : NEW_LINE INDENT par [ xpar ] = ypar NEW_LINE DEDENT elif ( Rank [ xpar ] > Rank [ ypar ] ) : NEW_LINE INDENT par [ ypar ] = xpar NEW_LINE DEDENT else : NEW_LINE INDENT par [ ypar ] = xpar NEW_LINE Rank [ xpar ] += 1 NEW_LINE DEDENT DEDENT def power ( a , m1 ) : NEW_LINE INDENT if ( m1 == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT elif ( m1 == 1 ) : NEW_LINE INDENT return a NEW_LINE DEDENT elif ( m1 == 2 ) : NEW_LINE INDENT return ( a * a ) % mod NEW_LINE DEDENT elif ( m1 & 1 ) : NEW_LINE INDENT return ( a * power ( power ( a , m1 // 2 ) , 2 ) ) % mod NEW_LINE DEDENT else : NEW_LINE INDENT return power ( power ( a , m1 // 2 ) , 2 ) % mod NEW_LINE DEDENT DEDENT def query ( l , r ) : NEW_LINE INDENT if l + r in m . keys ( ) : NEW_LINE INDENT m [ l + r ] = max ( m [ l + r ] , r ) NEW_LINE DEDENT else : NEW_LINE INDENT m [ l + r ] = max ( 0 , r ) NEW_LINE DEDENT DEDENT def possiblestrings ( ) : NEW_LINE INDENT initialize ( ) NEW_LINE for i in m : NEW_LINE INDENT x = i - m [ i ] NEW_LINE y = m [ i ] NEW_LINE while ( x < y ) : NEW_LINE INDENT Union ( x , y ) NEW_LINE x += 1 NEW_LINE y -= 1 NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( par [ i ] == i ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT DEDENT return power ( 26 , ans ) % mod NEW_LINE DEDENT n = 4 NEW_LINE query ( 1 , 3 ) NEW_LINE query ( 2 , 4 ) NEW_LINE print ( possiblestrings ( ) ) NEW_LINE