We know, ab=max(a,b)min(a,b)|a-b| = max(a,b) - min(a,b). This is also true for our operation type 2 in the problem. That is, for operation type 2 in range [L,R][L,R], the answer will be max(A[L],A[L+1])min(A[L],A[L+1])+max(A[L+1],A[L+2])min(A[L+1],A[L+2])++max(A[R1],A[R])min(A[R1],A[R])max(A[L],A[L+1]) - min(A[L],A[L+1]) + max(A[L+1],A[L+2]) - min(A[L+1],A[L+2]) + \dots + max(A[R-1],A[R]) - min(A[R-1],A[R]). Re-arranging this equation we can write (max(A[L],A[L+1])+max(A[L+1],A[L+2])++max(A[R1],A[R]))(min(A[L],A[L+1])+min(A[L+1],A[L+2])++min(A[R1],A[R]))( max(A[L],A[L+1]) + max(A[L+1],A[L+2]) + \dots + max(A[R-1],A[R]) ) - ( min(A[L],A[L+1]) + min(A[L+1],A[L+2]) + \dots + min(A[R-1],A[R]) ). Now, the problem is reduced to summation of maximum elements among all adjacent pairs in range [L,R][L,R] - summation of minimum elements among all adjacent pairs in range [L,R][L,R].

It can also be observed that after performing operation type 1 for a range [L,R][L,R], only the difference between the maximum and minimum elements of pairs (A[L1],A[L])(A[L-1],A[L]) and (A[R],A[R+1])( A[R],A[R+1] ) 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 (A[L1],A[L])(A[L-1],A[L]) and (A[R],A[R+1])(A[R],A[R+1]) 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: O(N×log(N))\mathcal{O}(N \times log(N)).

Statistics

73% Solution Ratio
hamza05Earliest, Dec '21
nh_nayeemFastest, 0.1s
nusuBotLightest, 11 MB
fahimcp495Shortest, 1473B
Toph uses cookies. By continuing you agree to our Cookie Policy.