text: Queries to count array elements greater than or equal to a given number with updates | C ++ program for the above approach ; Function to build a segment tree ; Check for base case ; Find mid point ; Recursively build the segment tree ; Function for push down operation on the segment tree ; Function to update the segment tree ; Complete overlap ; Find mid ; Perform push down operation on segment tree ; Recursively update the segment tree ; Function to process the query ; Base case ; Find mid ; Perform push down operation on segment tree ; Recursively calculate the result of the query ; Return the result ; Function to count the numbers which are greater than the given query ; Sort the input array ; Create segment tree of size 4 * n ; Build the segment tree ; Iterate over the queries ; Store result in array ; Update the elements in the given range ; Print the result of queries ; Driver Code ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void build ( vector < int > & sum , vector < int > & a , int l , int r , int rt ) { if ( l == r ) { sum [ rt ] = a [ l - 1 ] ; return ; } int m = ( l + r ) >> 1 ; build ( sum , a , l , m , rt << 1 ) ; build ( sum , a , m + 1 , r , rt << 1 1 ) ; } void pushDown ( vector < int > & sum , vector < int > & add , int rt , int ln , int rn ) { if ( add [ rt ] ) { add [ rt << 1 ] += add [ rt ] ; add [ rt << 1 1 ] += add [ rt ] ; sum [ rt << 1 ] += add [ rt ] * ln ; sum [ rt << 1 1 ] += add [ rt ] * rn ; add [ rt ] = 0 ; } } void update ( vector < int > & sum , vector < int > & add , int L , int R , int C , int l , int r , int rt ) { if ( L <= l && r <= R ) { sum [ rt ] += C * ( r - l + 1 ) ; add [ rt ] += C ; return ; } int m = ( l + r ) >> 1 ; pushDown ( sum , add , rt , m - l + 1 , r - m ) ; if ( L <= m ) update ( sum , add , L , R , C , l , m , rt << 1 ) ; if ( R > m ) update ( sum , add , L , R , C , m + 1 , r , rt << 1 1 ) ; } int query ( vector < int > & sum , vector < int > & add , int L , int R , int l , int r , int rt ) { if ( L <= l && r <= R ) { return sum [ rt ] ; } int m = ( l + r ) >> 1 ; pushDown ( sum , add , rt , m - l + 1 , r - m ) ; int ans = 0 ; if ( L <= m ) ans += query ( sum , add , L , R , l , m , rt << 1 ) ; if ( R > m ) ans += query ( sum , add , L , R , m + 1 , r , rt << 1 1 ) ; return ans ; } void sequenceMaintenance ( int n , int q , vector < int > & a , vector < int > & b , int m ) { sort ( a . begin ( ) , a . end ( ) ) ; vector < int > sum , add , ans ; sum . assign ( n << 2 , 0 ) ; add . assign ( n << 2 , 0 ) ; build ( sum , a , 1 , n , 1 ) ; for ( int i = 0 ; i < q ; i ++ ) { int l = 1 , r = n , pos = -1 ; while ( l <= r ) { int m = ( l + r ) >> 1 ; if ( query ( sum , add , m , m , 1 , n , 1 ) >= b [ i ] ) { r = m - 1 ; pos = m ; } else { l = m + 1 ; } } if ( pos == -1 ) ans . push_back ( 0 ) ; else { ans . push_back ( n - pos + 1 ) ; update ( sum , add , pos , n , - m , 1 , n , 1 ) ; } } for ( int i = 0 ; i < ans . size ( ) ; i ++ ) { cout << ans [ i ] << " ▁ " ; } } int main ( ) { int N = 4 ; int Q = 3 ; int M = 1 ; vector < int > arr = { 1 , 2 , 3 , 4 } ; vector < int > query = { 4 , 3 , 1 } ; sequenceMaintenance ( N , Q , arr , query , M ) ; return 0 ; }