We know, . This is also true for our operation type 2 in the problem. That is, for operation type 2 in range , the answer will be . Re-arranging this equation we can write . Now, the problem is reduced to summation of maximum elements among all adjacent pairs in range summation of minimum elements among all adjacent pairs in range .
It can also be observed that after performing operation type 1 for a range , only the difference between the maximum and minimum elements of pairs and may change. The difference between maximum and minimum elements of the rest of other adjacent pairs doesn’t change. So, we can use two segment trees (segment tree of pairs) to store the summation of maximum elements of adjacent pairs and the summation of minimum elements of adjacent pairs respectively. During operation type 1, we will update the maximum and minimum elements for pair and respectively using point query of segment tree. During operation type 2, we can get the range summation of maximum and minimum elements of adjacent pairs using that segment tree.
Time complexity: .