ABC339G: Smaller Sum from the last week's ABC had restrictions for online query and someone in the comment section was interested in knowing the alternate easier solution if the queries could be answered offline. So, I've written a short blog that talks about how to use sweep line to answer these 2 problems:
- You are given an array and several queries. A query consists of a subarray and $$$x$$$. Print the sum of all elements from this subarray that are $$$\leq x$$$.
- You are given a tree and some queries. In each query $$$(x, y, T)$$$ print YES if there is a path from $$$x$$$ to $$$y$$$ such that the maximum value on that path is $$$ \leq T$$$.
To help you solidify the concepts discussed, I've created 1 + 1 practice problems. You can access them https://mirror.codeforces.com/group/7Dn3ObOpau/contest/503852
https://cfstep.com/training/tutorials/general-techniques/answering-queries-offline-with-sweepline/
The problems are untested. If you see any issues, please let me know.
If you need any help or hints for the practice problem, you can ask on my Discord Server. In case you are interested, you can also checkout my youtube channel