Find the numbers of strings that can be formed after processing Q queries | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  2005 NEW_LINE #define mod  (int)(1e9 + 7) NEW_LINE int n , q ; int par [ N ] , Rank [ N ] ; map < int , int > m ; void initialize ( ) { for ( int i = 0 ; i <= n ; i ++ ) { par [ i ] = i ; Rank [ i ] = 0 ; } } int find ( int x ) { if ( par [ x ] != x ) par [ x ] = find ( par [ x ] ) ; return par [ x ] ; } void Union ( int x , int y ) { int xpar = find ( x ) ; int ypar = find ( y ) ; if ( Rank [ xpar ] < Rank [ ypar ] ) par [ xpar ] = ypar ; else if ( Rank [ xpar ] > Rank [ ypar ] ) par [ ypar ] = xpar ; else { par [ ypar ] = xpar ; Rank [ xpar ] ++ ; } } int power ( long long a , long long m1 ) { if ( m1 == 0 ) return 1 ; else if ( m1 == 1 ) return a ; else if ( m1 == 2 ) return ( 1LL * a * a ) % mod ; else if ( m1 & 1 ) return ( 1LL * a * power ( power ( a , m1 / 2 ) , 2 ) ) % mod ; else return power ( power ( a , m1 / 2 ) , 2 ) % mod ; } void query ( int l , int r ) { m [ l + r ] = max ( m [ l + r ] , r ) ; } int possiblestrings ( ) { initialize ( ) ; for ( auto i = m . begin ( ) ; i != m . end ( ) ; i ++ ) { int x = i -> first - i -> second ; int y = i -> second ; while ( x < y ) { Union ( x , y ) ; x ++ ; y -- ; } } int ans = 0 ; for ( int i = 1 ; i <= n ; i ++ ) if ( par [ i ] == i ) ans ++ ; return power ( 26 , ans ) % mod ; } int main ( ) { n = 4 ; query ( 1 , 3 ) ; query ( 2 , 4 ) ; cout << possiblestrings ( ) ; return 0 ; }