So, the main reason why I am writing this blog is because I think that it may be useful for everybody who struggles with ideas but knows hoe to code well.↵
↵
### First trick↵
↵
concerns every task of finding a minimum of the function among every continuous subsequence of the array if \begin{equation}f(l,r)\end{equation} is defined as \begin{equation} f(i, j) (1 ≤ i, j ≤ n)=q(i, j)^2 + g(i, j)^2\end{equation} And \begin{equation} g(l,r)=g(1,r)-g(1,l-1)\end{equation}↵
\begin{equation} q(l,r)=q(1,r)-q(1,l-1)\end{equation}↵
The way to solve this is by rewriting this formula into \begin{equation} f(i,j)=\sqrt{a^2+b^2}\end{equation} ↵
I think that if you learnt geometry in school, you certainly understand that this is eulers distance formula.↵
Now, if we want to find the minimum among every pair, we just have to find the minimum distance between 2 points on the grid!↵
And there actually exists an algorithm to compute this answer in O(n*logn) [it is described here](https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/)↵
↵
One of the tasks that can be solved using this: [problem:429D]↵
↵
↵
### Second trick↵
Concerns tasks in which we need to compute maximum of the same function. By transferring every point to the grid, we can solve this task geometrically,there exists an algorithm that solves it in O(n*logn) time (convex hull trick) [implementation and proof why it works](https://www.baeldung.com/cs/most-distant-pair-of-points)↵
↵
### Third trick ↵
↵
(the last one i can remember while being in a hospital because of my heart problems) ↵
↵
Is to use binary prefix trie if we have to find k-th MEX of the array. Also, it can be used if we have to compute the answer while XOR-ing every element of an array with some X (I can`t find the problem, so if someone knows what I am talking about, give me the link to that problem)↵
↵
Feel free to share some tricks in comments,to save this blog, to upvote it so other people also know these tricks and even maybe share their own trick knowledge, every trick written in comments will be added to this blog!↵
↵
### First trick↵
↵
concerns every task of finding a minimum of the function among every continuous subsequence of the array if \begin{equation}f(l,r)\end{equation} is defined as \begin{equation} f(i, j) (1 ≤ i, j ≤ n)=q(i, j)^2 + g(i, j)^2\end{equation} And \begin{equation} g(l,r)=g(1,r)-g(1,l-1)\end{equation}↵
\begin{equation} q(l,r)=q(1,r)-q(1,l-1)\end{equation}↵
The way to solve this is by rewriting this formula into \begin{equation} f(i,j)=\sqrt{a^2+b^2}\end{equation} ↵
I think that if you learnt geometry in school, you certainly understand that this is eulers distance formula.↵
Now, if we want to find the minimum among every pair, we just have to find the minimum distance between 2 points on the grid!↵
And there actually exists an algorithm to compute this answer in O(n*logn) [it is described here](https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/)↵
↵
One of the tasks that can be solved using this: [problem:429D]↵
↵
↵
### Second trick↵
Concerns tasks in which we need to compute maximum of the same function. By transferring every point to the grid, we can solve this task geometrically,there exists an algorithm that solves it in O(n*logn) time (convex hull trick) [implementation and proof why it works](https://www.baeldung.com/cs/most-distant-pair-of-points)↵
↵
### Third trick ↵
↵
(the last one i can remember while being in a hospital because of my heart problems) ↵
↵
Is to use binary prefix trie if we have to find k-th MEX of the array. Also, it can be used if we have to compute the answer while XOR-ing every element of an array with some X (I can`t find the problem, so if someone knows what I am talking about, give me the link to that problem)↵
↵
Feel free to share some tricks in comments,to save this blog, to upvote it so other people also know these tricks and even maybe share their own trick knowledge, every trick written in comments will be added to this blog!↵
