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

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

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

Feel free to share some tricks in comments, every trick that is useful will be added to this blog!

(/predownloaded/f9/f8/f9f87fcbbc871878c19b4a9c83eabf9e4315997d.jpg)