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.