Battalion Strength
Contest: CodeCraft-20 (Div. 2)
Difficulty rating: 2800
Tags: data structures, divide and conquer, probabilities

There are $$$n$$$ officers in the Army of Byteland. Each officer has some power associated with him. The power of the $$$i$$$-th officer is denoted by $$$p_{i}$$$. As the war is fast approaching, the General would like to know the strength of the army.

The strength of an army is calculated in a strange way in Byteland. The General selects a random subset of officers from these $$$n$$$ officers and calls this subset a battalion.(All $$$2^n$$$ subsets of the $$$n$$$ officers can be chosen equally likely, including empty subset and the subset of all officers).

The strength of a battalion is calculated in the following way:

Let the powers of the chosen officers be $$$a_{1},a_{2},\ldots,a_{k}$$$, where $$$a_1 \le a_2 \le \dots \le a_k$$$. The strength of this battalion is equal to $$$a_1a_2 + a_2a_3 + \dots + a_{k-1}a_k$$$. (If the size of Battalion is $$$\leq 1$$$, then the strength of this battalion is $$$0$$$).

The strength of the army is equal to the expected value of the strength of the battalion.

As the war is really long, the powers of officers may change. Precisely, there will be $$$q$$$ changes. Each one of the form $$$i$$$ $$$x$$$ indicating that $$$p_{i}$$$ is changed to $$$x$$$.

You need to find the strength of the army initially and after each of these $$$q$$$ updates.

Note that the changes are permanent.

The strength should be found by modulo $$$10^{9}+7$$$. Formally, let $$$M=10^{9}+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$p/q$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q\not\equiv 0 \bmod M$$$). Output the integer equal to $$$p\cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \leq x < M$$$ and $$$x ⋅ q \equiv p \bmod M$$$).

Input format:
The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 3⋅10^{5}$$$)  — the number of officers in Byteland's Army.

The second line contains $$$n$$$ integers $$$p_{1},p_{2},\ldots,p_{n}$$$ ($$$1 \leq p_{i} \leq 10^{9}$$$).

The third line contains a single integer $$$q$$$ ($$$1 \leq q \leq 3⋅10^{5}$$$)  — the number of updates.

Each of the next $$$q$$$ lines contains two integers $$$i$$$ and $$$x$$$ ($$$1 \leq i \leq n$$$, $$$ 1 \leq x \leq 10^{9}$$$), indicating that $$$p_{i}$$$ is updated to $$$x$$$ .

Output format:
In the first line output the initial strength of the army.

In $$$i$$$-th of the next $$$q$$$ lines, output the strength of the army after $$$i$$$-th update.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In first testcase, initially, there are four possible battalions

- {} Strength = $$$0$$$
- {$$$1$$$} Strength = $$$0$$$
- {$$$2$$$} Strength = $$$0$$$
- {$$$1,2$$$} Strength = $$$2$$$

After changing $$$p_{1}$$$ to $$$2$$$, strength of battallion {$$$1,2$$$} changes to $$$4$$$, so strength of army becomes $$$1$$$.

After changing $$$p_{2}$$$ to $$$1$$$, strength of battalion {$$$1,2$$$} again becomes $$$2$$$, so strength of army becomes $$$\frac{1}{2}$$$.

Example input:
2
1 2
2
1 2
2 1

Example output:
500000004
1
500000004

Example input:
4
1 2 3 4
4
1 5
2 5
3 5
4 5

Example output:
625000011
13
62500020
375000027
62500027

Editorial:
First lets try to find the initial strength of the army. Let $$$p_1,p_2,\ldots,p_n$$$ be the powers of officers in sorted order. .
Consider a pair ($$$i,j$$$) ($$$i < j$$$) and find how much it contributes to the answer, the term $$$p_i \cdot p_j$$$ will be present in the strength of the subsets in which both $$$i$$$ and $$$j$$$ are present and there is no $$$k$$$ such that $$$i < k < j$$$. Probability of this happening is $$$\frac {1}{2^{j-i+1}}$$$. By linearity of expectation we can say that the contribution of ($$$i,j$$$) to the strength of the army is $$$p_i \cdot p_j \cdot \frac {1}{2^{j-i+1}}$$$.
So the strenth of the army can be written as $$$S = \sum_{i=1}^{n} \sum_{j=i+1}^{n} prob_{i,j} \cdot p_i \cdot p_j $$$ where $$$prob_{i,j} = \frac {1}{2^{j-i+1}}$$$.
We can keep a sorted array having $$$p_1,p_2,\ldots,p_n$$$, we can maintain a prefix sum of $$$pref_i$$$ = $$$p_i \cdot 2^{i-1}$$$,so $$$S = \sum_{j=1}^{n} pref_{j-1} \cdot \frac{p_j}{2^{j}}$$$. But this will not help in handling the updtes.
To support updates, we need to process queries offline and use coordinate compression such that all powers lie in range $$$(1,10^6)$$$. We can build a segment tree on the compressed powers.
For each node of the segment tree, let its range be $$$(s,e)$$$, consider that powers(mapped values by coordinate compression) $$$p_1,p_2,\ldots,p_k$$$ line in the range of this node ($$$s \leq p_1 \leq p_2 \leq \ldots \leq p_k \leq e$$$).
At each node, we need to maintain 4 values.
• $$$val: \sum_{i=1}^{k} \sum_{j=i+1}^{k} prob_{i,j} \cdot p_i \cdot p_j$$$
• $$$Lval: \sum_{i=1}^{k} p_i \cdot 2^{i-1}$$$
• $$$Rval: \sum_{j=1}^{k} \frac{p_j}{2^{j}}$$$
• $$$count: k$$$
If we map each power to a unique value, the computation for this values at leaf node $$$(s=e)$$$ is trivial. If some power $$$p$$$ in the initial set is mapped to s, then values for this node are as follows
• $$$val: 0$$$
• $$$Lval: p$$$
• $$$Rval: \frac{p}{2}$$$
• $$$count: 1$$$.
Lets try to compute these 4 values for non-leaf nodes of the segment tree. (lc and rc denote left and right children of the current node). If we try to write break these values in terms of their counterparts in lc and rc, we can easily write them as:
• $$$val : val_{lc}+val_{rc}+\frac{Lval_{lc} \cdot Rval_{rc}}{2^{count_{lc}}}$$$
• $$$Lval : Lval_{lc} + Lval_{rc} \cdot 2^{count_{lc}}$$$
• $$$Rval : Rval_{lc} + \frac {Rval_{rc}}{2^{count_{lc}}}$$$
• $$$count : count_{lc} + count_{rc}$$$
Whenver we get a query ,we will need to update 2 leaves, reduce count of the power for old $$$p_i$$$ and increase the count of the new_power $$$p_i = x$$$. Answer to our problem would be $$$val$$$ at root node of the segment tree.
Time Complexity: $$$O((n+q)log(n))$$$