Queries to count array elements greater than or equal to a given number with updates | Java 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
import java . io . * ; import java . util . * ; class GFG { static void build ( Vector < Integer > sum , Vector < Integer > a , int l , int r , int rt ) { if ( l == r ) { sum . set ( rt , a . get ( l - 1 ) ) ; return ; } int m = ( l + r ) >> 1 ; build ( sum , a , l , m , rt << 1 ) ; build ( sum , a , m + 1 , r , rt << 1 1 ) ; } static void pushDown ( Vector < Integer > sum , Vector < Integer > add , int rt , int ln , int rn ) { if ( add . get ( rt ) != 0 ) { add . set ( rt << 1 , add . get ( rt ) ) ; add . set ( rt << 1 | 1 , add . get ( rt ) ) ; sum . set ( rt << 1 , sum . get ( rt << 1 ) + add . get ( rt ) * ln ) ; sum . set ( rt << 1 | 1 , sum . get ( rt << 1 1 ) + add . get ( rt ) * rn ) ; add . set ( rt , 0 ) ; } } static void update ( Vector < Integer > sum , Vector < Integer > add , int L , int R , int C , int l , int r , int rt ) { if ( L <= l && r <= R ) { sum . set ( rt , sum . get ( rt ) + C * ( r - l + 1 ) ) ; add . set ( rt , add . get ( 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 ) ; } } static int query ( Vector < Integer > sum , Vector < Integer > add , int L , int R , int l , int r , int rt ) { if ( L <= l && r <= R ) { return sum . get ( 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 ; } static void sequenceMaintenance ( int n , int q , Vector < Integer > a , Vector < Integer > b , int m ) { Collections . sort ( a ) ; Vector < Integer > sum = new Vector < Integer > ( ) ; Vector < Integer > ad = new Vector < Integer > ( ) ; Vector < Integer > ans = new Vector < Integer > ( ) ; for ( int i = 0 ; i < ( n << 2 ) ; i ++ ) { sum . add ( 0 ) ; ad . add ( 0 ) ; } build ( sum , a , 1 , n , 1 ) ; for ( int i = 0 ; i < q ; i ++ ) { int l = 1 , r = n , pos = - 1 ; while ( l <= r ) { m = ( l + r ) >> 1 ; if ( query ( sum , ad , m , m , 1 , n , 1 ) >= b . get ( i ) ) { r = m - 1 ; pos = m ; } else { l = m + 1 ; } } if ( pos == - 1 ) { ans . add ( 0 ) ; } else { ans . add ( n - pos + 1 ) ; update ( sum , ad , pos , n , - m , 1 , n , 1 ) ; } } for ( int i = 0 ; i < ans . size ( ) ; i ++ ) { System . out . print ( ans . get ( i ) + " ▁ " ) ; } } public static void main ( String [ ] args ) { int N = 4 ; int Q = 3 ; int M = 1 ; Vector < Integer > arr = new Vector < Integer > ( ) ; arr . add ( 1 ) ; arr . add ( 2 ) ; arr . add ( 3 ) ; arr . add ( 4 ) ; Vector < Integer > query = new Vector < Integer > ( ) ; query . add ( 4 ) ; query . add ( 3 ) ; query . add ( 1 ) ; sequenceMaintenance ( N , Q , arr , query , M ) ; } }