## Editorial for DMOPC '18 Contest 5 P5 - A Hat Problem

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: r3mark

Each person has two choices, so there are possibilities. Trying each of these possibilities passes in time for subtask 1.

Time Complexity:

For the second subtask, let be the least unhappiness if person leaves without trading the next person. Say that they leave with the hat originally from person . For that hat to have travelled all the way there, person must have not traded with the next person and everyone from to must have. It is then easy to see that in this case,

The sum can be computed in with a prefix sum array.

Time Complexity:

For the final subtask, we analyze the from above. Splitting the absolute value into two cases yields the following:

Note that each sum can be split into a component that depends only on , and a component that depends only on . So we create two segment trees storing the component depending on . More precisely, we update each segment tree at index with value and . Then we can query the two segment trees to compute each value.

Time Complexity: