For any query (x1, x2, y), **ans1** stores answer for query(0, x1, y) and **ans2** stores answer for query(0, x2, y). So our final answer becomes **(ans2 - ans1)** which will be storing answer for query (x1, x2, y).

Kind of inclusion and exclusion on the count of intersection.

Updated my solution with comments.

Thanks. You had already explained your method. I asked for the comments from the main author of the post. But thanks ,now your answer code is really very simple to understand.

Awesome approach!

I solved it using policy based data structures (my solution here). Did anybody else use this same approach?

I thought about it during the contest but was too lazy to study PBDS. It is also kind of an overkill for this question i guess Can you share some good resources to learn it?

Excellent solution. Interestingly, I thought of this approach, but could not optimize the algo/code properly.

I mean all you have to do is type the header files and initialiser and you get a data structure that supports addition, deletion, find, and no. of elements less than given x in log n time. Basically set, but better.