Queries to count sum of rows and columns of a Matrix present in given ranges | C ++ program for the above approach ; Function to search for the leftmost index of given number ; Initialize low , high and ans ; Stores mid ; If A [ mid ] >= num ; Function to search for the rightmost index of given number ; Initialise low , high and ans ; Stores mid ; If A [ mid ] <= num ; Update ans ; Update mid ; Update high ; Function to preprocess the matrix to execute the queries ; Stores the sum of each row ; Stores the sum of each col ; Traverse the matrix and calculate sum of each row and column ; Insert all row sums in sum_list ; Insert all column sums in sum_list ; Sort the array in ascending order ; Traverse the array queries [ ] [ ] ; Search the leftmost index of L ; Search the rightmost index of R ; Driver Code ; Given dimensions of matrix ; Given matrix ; Given number of queries ; Given queries ; Function call to count the number row - sums and column - sums present in the given ranges
#include <bits/stdc++.h> NEW_LINE using namespace std ; int left_search ( vector < int > A , int num ) { int low = 0 , high = A . size ( ) - 1 ; int ans = 0 ; while ( low <= high ) { int mid = low + ( high - low ) / 2 ; if ( A [ mid ] >= num ) { ans = mid ; high = mid - 1 ; } else { low = mid + 1 ; } } return ans ; } int right_search ( vector < int > A , int num ) { int low = 0 , high = A . size ( ) - 1 ; int ans = high ; while ( low <= high ) { int mid = low + ( high - low ) / 2 ; if ( A [ mid ] <= num ) { ans = mid ; low = mid + 1 ; } else { high = mid - 1 ; } } return ans ; } void totalCount ( vector < vector < int > > A , int N , int M , vector < vector < int > > queries , int Q ) { vector < int > row_sum ( N ) ; vector < int > col_sum ( N ) ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { row_sum [ i ] += A [ i ] [ j ] ; col_sum [ j ] += A [ i ] [ j ] ; } } vector < int > sum_list ; for ( int i = 0 ; i < N ; i ++ ) sum_list . push_back ( row_sum [ i ] ) ; for ( int i = 0 ; i < M ; i ++ ) sum_list . push_back ( col_sum [ i ] ) ; sort ( sum_list . begin ( ) , sum_list . end ( ) ) ; for ( int i = 0 ; i < Q ; i ++ ) { int L = queries [ i ] [ 0 ] ; int R = queries [ i ] [ 1 ] ; int l = left_search ( sum_list , L ) ; int r = right_search ( sum_list , R ) ; cout << r - l + 1 << " ▁ " ; } } int main ( ) { int N = 3 , M = 2 ; vector < vector < int > > A = { { 13 , 3 } , { 9 , 4 } , { 6 , 10 } } ; int Q = 2 ; vector < vector < int > > queries = { { 10 , 20 } , { 25 , 35 } } ; totalCount ( A , N , M , queries , Q ) ; }