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!