Count subarrays for every array element in which they are the minimum | C ++ 14 program for the above approach ; Function to find the boundary of every element within which it is minimum ; Perform Binary Search ; Find mid m ; Update l ; Update r ; Inserting the index ; Function to required count subarrays ; Stores the indices of element ; Initialize the output array ; Left boundary , till the element is smallest ; Right boundary , till the element is smallest ; Calculate the number of subarrays based on its boundary ; Adding cnt to the ans ; Driver Code ; Given array arr [ ] ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int binaryInsert ( vector < int > & boundary , int i ) { int l = 0 ; int r = boundary . size ( ) - 1 ; while ( l <= r ) { int m = ( l + r ) / 2 ; if ( boundary [ m ] < i ) l = m + 1 ; else r = m - 1 ; } boundary . insert ( boundary . begin ( ) + l , i ) ; return l ; } vector < int > countingSubarray ( vector < int > arr , int n ) { unordered_map < int , int > index ; for ( int i = 0 ; i < n ; i ++ ) index [ arr [ i ] ] = i ; vector < int > boundary = { -1 , n } ; sort ( arr . begin ( ) , arr . end ( ) ) ; vector < int > ans ( n , 0 ) ; for ( int num : arr ) { int i = binaryInsert ( boundary , index [ num ] ) ; int l = boundary [ i ] - boundary [ i - 1 ] - 1 ; int r = boundary [ i + 1 ] - boundary [ i ] - 1 ; int cnt = l + r + l * r + 1 ; ans [ index [ num ] ] += cnt ; } return ans ; } int main ( ) { int N = 5 ; vector < int > arr = { 3 , 2 , 4 , 1 , 5 } ; auto a = countingSubarray ( arr , N ) ; cout << " [ " ; int n = a . size ( ) - 1 ; for ( int i = 0 ; i < n ; i ++ ) cout << a [ i ] << " , ▁ " ; cout << a [ n ] << " ] " ; return 0 ; }