All Tracks Data Structures Advanced Data Structures Problem

Micro and Mike
Tag(s):

Data Structures, Medium, Segment Trees

Problem
Editorial
Analytics

Micro and Mike are doing some research on arrays. For experiment purpose, they purchased an array A having N integers. They have a board which displays Health of their array.

Health of an array is defined as sum of fitness-factor for all possible non-empty sub-sequences of the array. Fitness-factor of a non-empty sub-sequence is defined as product of maximum and minimum element present in the sub-sequence.

An array P is called subsequence of another array Q, if P can be obtained by deleting zero or more elements of Q.

They want the value on the board to get updated each time they change any element of the array. They've written a program for it. Their program takes the array as input, then allows them to perform Q operations. Each operation is defined as:
\(x \; v\): Change \(A[x]\) to v.
After each operation their program prints the Health of the new array. But they are not sure that their program is correct. So, they want you to write a program that performs the same task, so that they can compare their output against yours.

Input:
First line consists of two space separated integers denoting N and Q.
Second line consists of N space separated integers denoting the array A.
Each of the following Q lines consists of a single operation as defined.

Output:
After performing each operation print the health of the new array in a new line. Since output can be large, print it modulo \(10^9+7\).

Constraints:
\(1 \le N \le 10^5\)
\(1 \le Q \le 2 \times 10^5\)
\(1 \le A[i], v \le 10^9\)
\(1 \le x \le N\)

SAMPLE INPUT
3 2
1 2 3
2 4
1 3
SAMPLE OUTPUT
49
79
Explanation

After performing \(1^{st}\) operation array will be \([1, 4, 3]\). All possible sub-sequences along with their fitness factor are:
1 - 1
4 - \(16\)
3 - 9
\([1, 4]\) - 4
\([1, 3]\) - 3
\([4, 3]\) - \(12\)
\([1, 4, 3]\) - 4
Now, health of the array is sum of fitness factor of all sub-sequences which is \(49\).

After performing \(2^{nd}\) operation array will be \([3, 4, 3]\). All possible sub-sequences along with their fitness factor are:
3 - 9
4 - \(16\)
3 - 9
\([3, 4]\) - \(12\)
\([3, 3]\) - 9
\([4, 3]\) - \(12\)
\([3, 4, 3]\) - \(12\)
Now, health of the array is sum of fitness factor of all sub-sequences which is \(79\).

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Easy '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?