Contest Duration: - (local time) (120 minutes) Back to Home

## F - Max Matrix Editorial by en_translator

For convenience we use the matrix described in Sample $$!$$.
Let us consider processing a query of type $$1$$.
We regard the operation of updating $$a_i$$ from $$x$$ to $$y$$ as first removing the $$i$$-th row of the matrix and then reviving the new $$i$$-th row after replaced with $$y$$.
Then what we want is the sum of the $$i$$-th row when $$a_i = x$$.
This is equal to (the number of such $$j$$ that $$b_j < x$$) $$\times x$$ + (the sum of $$b_j$$ such that $$b_j \ge x$$).
Since $$b_j$$ is updated by type $$2$$ too, we need data structures with following requirements:

• manage the set of numbers
• support removing and adding numbers
• find the number of elements less than a specified value
• find the sum of elements greater than a specified value

One can use a self-balancing binary search tree, but it can alternatively solved with coordinates compression and segment trees. Specifically, one can manage a sequence “$$c_i$$: the number of occurrence of $$i$$ in $$b$$” with a segment tree (with coordinates $$i$$ being compressed properly) so as to find the number of elements with less than a specific value, and similarly find the sum of elements with more than a specific value.

One can similarly process type $$2$$ by swapping $$a$$ and $$b$$ and using the same data structure.

posted:
last update: