This problem can be solved using $Heavy$ $Light$ $Decomposition$ $(HLD)$.
Let's think about a much simpler problem:
You are given an array of integers. You have to $Add$ or $Remove$ integer 1 with all the values of a given range. And for the $Answer$ types queries, you have to find the maximum value of a given range, and tell the number of occurrences of the maximum value in the given range.
Can you solve this using $Segment$ $Tree$?
If the answer is yes, you are good to go!
Apply this type of segment tree for update paths using $HLD$.
And for $Answer$ type queries, query on whole tree!

Contributors

Statistics

100% Solution Ratio
BigBagEarliest, Mar '21
nusuBotFastest, 0.2s
serotoninLightest, 20 MB
Deshi_TouristShortest, 2308B
Toph uses cookies. By continuing you agree to our Cookie Policy.