I've found an interesting problem in hackerrank. But couldn't solve it. I've tried so many ways, but no one can pass the time limit. That's why I've decided to seek some help from you guys :) Here is the problem link. If anyone have an idea to solve it, please share your thoughts :)

UPD: Solved it with mo's algorithm + binary index tree. Thanks for the hint mkirsche :)