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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, 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