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](https://codeforces.me/contest/2121/problem/F) 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](https://cses.fi/problemset/task/1660) on CSES and this is the [solution](https://cses.fi/paste/50088a50112e4c8e9ff3b6/)↵
↵
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](https://codeforces.me/contest/2121/submission/325043828)↵
↵
some practicing problems on that technique ↵
↵
- [atcoder 407 f](https://atcoder.jp/contests/abc407/tasks/abc407_f)↵
↵
- [j weird sum](https://codeforces.me/gym/101801/problem/J)↵
↵
- [1777 F](https://codeforces.me/contest/1777/problem/F)
↵
- 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](https://codeforces.me/contest/2121/problem/F) 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](https://cses.fi/problemset/task/1660) on CSES and this is the [solution](https://cses.fi/paste/50088a50112e4c8e9ff3b6/)↵
↵
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](https://codeforces.me/contest/2121/submission/325043828)↵
↵
some practicing problems on that technique ↵
↵
- [atcoder 407 f](https://atcoder.jp/contests/abc407/tasks/abc407_f)↵
↵
- [j weird sum](https://codeforces.me/gym/101801/problem/J)↵
↵
- [1777 F](https://codeforces.me/contest/1777/problem/F)
