HI! Recently I learned new technique I want to share which solve this type of problems
- You are given array $$$a$$$ and you want to do something with subarrays whose maximum or minimum element are Important to you somehow
The general method is to when we are solving for the whole array , we will divide the array from the maximum/minimum and solve the left and right part like any normal d&c but we will make the d&c return a data structure that is built on this section of the array only which will help us on getting the answer , the only remaining thing is to answer the about the subarrays whose maximum/minimum is the place we divided from it , so we need to consider the subarrays whose left part less than or equal to the index $$$i$$$ that we divide from and the right end of the subarray belong to the right part of the index $$$i$$$. we will use small to large merging here , we will identify which part is the smaller , $$$[l , i]$$$ or $$$[i , r]$$$ and we will brute force on this part while getting the answer from the data structure built on top of the other part , then merge the 2 data structure and return it , probably we must use pointers to avoid copy the data structure among the recursion calls.
Like recent div3 problem $$$F$$$ , You are given an array of integers $$$(a_1 , a_2 , ... , a_n)$$$ and two integers $$$(s , x)$$$ and we need to count the number of subarrays whose sum is $$$s$$$ and maximum is $$$x$$$.
we know that if we just want to count how many subarray with a certain sum , we can build the prefix sum and we need to count how many pair $$$(l , r)$$$ such that $$$(prefix[r] - prefix[l - 1]) = s$$$ and we can solve it by scanning the array while we have frequency array or map to record what we saw so far like this standard problem on CSES and this is the solution
but in our problem we need to count only pairs $$$(l , r)$$$ whose sum is $$$s$$$ and maximum is $$$x$$$ , so we can apply the d&c technique here and we divide and conquer on maximum while we return a map that represent the frequency of the range we are solving , frequency of the prefix sum values and if the maximum is not the $$$x$$$ we want we just merge the 2 maps , by small to large merging , and if $$$x$$$ is the value we search for then , we loop on the small part $$$[l , idx]$$$ , $$$[idx , r]$$$ while using the other part data structure to answer those subarrays whose pass through $$$idx$$$ , my solution
some practicing problems on that technique
