https://codeforces.com/blog/entry/113075
today i read this blog and found a very useful trick i will introduce it to such interval problems consider constructing a cartesian coordinate system for an interval $$$[x,y]$$$ and mapping it to the point $$$(x,y)$$$ for the query operation stated in the blog given $$$(l,r)$$$ translate to coordinate points is to ask how many points there are in a certain rectangle then the problem was transformed into a simple one then lets say mos algo put each $$$[l,r]$$$ on the axis then the problem becomes that you can go up down left right and ask for the minimum number of times to traverse all the points so that you can understand mo more intuitively lets take another example of a topic i encountered while talking with my friend my friend asked there is an array that supports swapping two numbers and querying the number of inverse pairs my friend wants to know if there is anything below $$$O(n\log^2n)$$$ just put $$$(i,a_i)$$$ to the coordinate points then the problem becomes to support modifying the coordinates of a point and querying the number of points inside a rectangle it is impossible to go below $$$O(n\log^2n)$$$ you can see that this trick is very helpful to think about the problem try using this method of thinking when you encounter problems with interval bounded comparisons
Comments (0)
