## Editorial for UTS Open '18 P7 - Gossip Network

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: PlasmaVortex

Each time a piece of news is announced, perform a DFS to update the total interest value heard by each person. This allows you to answer type-2 queries in .

Time Complexity:

Use a BIT-like data structure, where left[] is the sum of the interest values heard by student for any news originating from the students to the left of , where denotes the largest power of dividing (this is i&-i in C++). Construct a second BIT with right instead of left, then we can update and query in time.

Time Complexity: