Count number of increasing sub | C # implementation of the approach ; Segment tree array ; Function for point update In segment tree ; Base case ; If l == r == up ; Mid element ; Updating the segment tree ; Function for the range sum - query ; Base case ; Mid element ; Calling for the left and the right subtree ; Function to return the count ; Copying array arr to sort it ; Sorting array brr ; Map to store the rank of each element ; dp array ; To store the readonly answer ; Updating the dp array ; Rank of the element ; Solving the dp - states using segment tree ; Updating the readonly answer ; Updating the segment tree ; Returning the readonly answer ; Driver code
using System ; using System . Collections . Generic ; class GFG { static readonly int N = 10000 ; static int [ ] seg = new int [ 3 * N ] ; static int update ( int In , int l , int r , int up_in , int val ) { if ( r < up_in l > up_in ) return seg [ In ] ; if ( l == up_in && r == up_in ) return seg [ In ] = val ; int m = ( l + r ) / 2 ; return seg [ In ] = update ( 2 * In + 1 , l , m , up_in , val ) + update ( 2 * In + 2 , m + 1 , r , up_in , val ) ; } static int query ( int In , int l , int r , int l1 , int r1 ) { if ( l > r ) return 0 ; if ( r < l1 l > r1 ) return 0 ; if ( l1 <= l && r <= r1 ) return seg [ In ] ; int m = ( l + r ) / 2 ; return query ( 2 * In + 1 , l , m , l1 , r1 ) + query ( 2 * In + 2 , m + 1 , r , l1 , r1 ) ; } static int findCnt ( int [ ] arr , int n ) { int [ ] brr = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) brr [ i ] = arr [ i ] ; Array . Sort ( brr ) ; Dictionary < int , int > r = new Dictionary < int , int > ( ) ; for ( int i = 0 ; i < n ; i ++ ) r . Add ( brr [ i ] , i + 1 ) ; int [ ] dp = new int [ n ] ; int ans = 0 ; for ( int i = n - 1 ; i >= 0 ; i -- ) { int rank = r [ arr [ i ] ] ; dp [ i ] = 1 + query ( 0 , 0 , n - 1 , rank , n - 1 ) ; ans += dp [ i ] ; update ( 0 , 0 , n - 1 , rank - 1 , dp [ i ] + query ( 0 , 0 , n - 1 , rank - 1 , rank - 1 ) ) ; } return ans ; } public static void Main ( String [ ] args ) { int [ ] arr = { 1 , 2 , 10 , 9 } ; int n = arr . Length ; Console . Write ( findCnt ( arr , n ) ) ; } }