[education] A useful trick for interval relations

Revision en1, by ShaoNianTongXue5307, 2023-02-21 11:00:07

https://mirror.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

I hope you enjoy my blog!!!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ShaoNianTongXue5307 2023-02-21 11:00:07 1398 Initial revision (published)