Subset Trick
Contest: Codeforces Round 707 (Div. 1, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 3300
Tags: binary search, data structures

Vanya invented an interesting trick with a set of integers.

Let an illusionist have a set of positive integers $$$S$$$. He names a positive integer $$$x$$$. Then an audience volunteer must choose some subset (possibly, empty) of $$$S$$$ without disclosing it to the illusionist. The volunteer tells the illusionist the size of the chosen subset. And here comes the trick: the illusionist guesses whether the sum of the subset elements does not exceed $$$x$$$. The sum of elements of an empty subset is considered to be $$$0$$$.

Vanya wants to prepare the trick for a public performance. He prepared some set of distinct positive integers $$$S$$$. Vasya wants the trick to be successful. He calls a positive number $$$x$$$ unsuitable, if he can't be sure that the trick would be successful for every subset a viewer can choose.

Vanya wants to count the number of unsuitable integers for the chosen set $$$S$$$.

Vanya plans to try different sets $$$S$$$. He wants you to write a program that finds the number of unsuitable integers for the initial set $$$S$$$, and after each change to the set $$$S$$$. Vanya will make $$$q$$$ changes to the set, and each change is one of the following two types:

- add a new integer $$$a$$$ to the set $$$S$$$, or
- remove some integer $$$a$$$ from the set $$$S$$$.

Input format:
The first line contains two integers $$$n$$$, $$$q$$$ ($$$1 \leq n, q \leq 200\,000$$$) — the size of the initial set $$$S$$$ and the number of changes.

The next line contains $$$n$$$ distinct integers $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \leq s_i \leq 10^{13}$$$) — the initial elements of $$$S$$$.

Each of the following $$$q$$$ lines contain two integers $$$t_i$$$, $$$a_i$$$ ($$$1 \leq t_i \leq 2$$$, $$$1 \leq a_i \leq 10^{13}$$$), describing a change:

- If $$$t_i = 1$$$, then an integer $$$a_i$$$ is added to the set $$$S$$$. It is guaranteed that this integer is not present in $$$S$$$ before this operation.
- If $$$t_i = 2$$$, then an integer $$$a_i$$$ is removed from the set $$$S$$$. In is guaranteed that this integer is present in $$$S$$$ before this operation.

Output format:
Print $$$q + 1$$$ lines.

In the first line print the number of unsuitable integers for the initial set $$$S$$$. In the next $$$q$$$ lines print the number of unsuitable integers for $$$S$$$ after each change.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first example the initial set is $$$S = \{1, 2, 3\}$$$. For this set the trick can be unsuccessful for $$$x \in \{1, 2, 3, 4\}$$$. For example, if $$$x = 4$$$, the volunteer can choose the subset $$$\{1, 2\}$$$ with sum $$$3 \leq x$$$, and can choose the subset $$$\{2, 3\}$$$ with sum $$$5 > x$$$. However, in both cases the illusionist only know the same size of the subset ($$$2$$$), so he can't be sure answering making a guess. Since there is only one subset of size $$$3$$$, and the sum of each subset of smaller size does not exceed $$$5$$$, all $$$x \ge 5$$$ are suitable.

Example input:
3 11
1 2 3
2 1
1 5
1 6
1 7
2 6
2 2
2 3
1 10
2 5
2 7
2 10

Example output:
4
1
6
12
19
13
8
2
10
3
0
0

Editorial:
Let $$$S = \{a_1, a_2, \ldots, a_n\}$$$, where $$$a_1 < a_2 < \ldots < a_n$$$.
Let's calculate the number of good numbers from $$$0$$$ to $$$sum(X) - 1$$$. To get the answer to our problem we should subtract this value from $$$sum(S)$$$.
Let's suppose that $$$0 \leq x < sum(X)$$$ is good. It is easy to see that it is equivalent to $$$a_{n - k + 1} + \ldots + a_{n} \leq x < a_{1} + \ldots + a_{k+1}$$$ for some $$$0 \leq k < n$$$.
So to calculate the required number of good numbers we should find the length of the union of intervals $$$[a_{n - k + 1} + \ldots + a_{n}, a_{1} + \ldots + a_{k+1})$$$ for all $$$0 \leq k < n$$$.
We can note two things:
• some of these intervals are empty
• all non-empty intervals does not intersect with each other
So the number we want to find is just $$$\sum\limits_{k=0}^{n-1} \max{(a_{1} + \ldots + a_{k+1} - a_{n - k + 1} - \ldots - a_{n}, 0)}$$$.
Let's call $$$f(k) = a_{1} + \ldots + a_{k+1} - a_{n - k + 1} - \ldots - a_{n}$$$. Let's note two simply things:
• $$$f(k) = f(n - 1 - k)$$$
• $$$f(x) \geq f(y)$$$ if $$$x \leq y \leq \frac{n-1}{2}$$$
Let's use them. First of all let's find $$$\sum\limits_{k=0}^{\frac{n-1}{2}} \max{(f(k), 0)}$$$. We can simply calculate the sum we need from it because we should just multiply this sum by $$$2$$$ and possibly subtract the number from the middle (if $$$n$$$ is odd).
Let's note that in the sum $$$\sum\limits_{k=0}^{\frac{n-1}{2}} \max{(f(k), 0)}$$$ some first summands are $$$> 0$$$, others are equal to $$$0$$$ (because $$$0$$$ will be bigger in the maximum).
Let's find the minimal $$$l \leq \frac{n-1}{2}$$$, such that $$$f(l) \leq 0$$$ using binary search. After that we should calculate $$$\sum\limits_{k=0}^{l-1} f(k) = \sum\limits_{k=0}^{l-1} (a_{1} + \ldots + a_{k+1} - a_{n - k + 1} - \ldots - a_{n}) = \sum\limits_{i=0}^{l} a_i (l - i) - \sum\limits_{i=n-l+1}^{n} a_i (i + l - n)$$$.
So what values we should be able to calculate to solve the problem?
• The sum of numbers on prefix $$$\sum\limits_{i=0}^{k} a_i$$$. Using two queries of this type we can calculate $$$f(k)$$$.
• The sum of numbers multiplied by index on prefix $$$\sum\limits_{i=0}^{k} a_i i$$$. We can calculate the final answer using this query.
To answer these queries effectively let's use the segment tree. Initially let's find all numbers that will be in $$$S$$$ in some moment (we can do it because we have the list of all queries). We will make a segment tree on this array, where we will write $$$0$$$, if there is no such number currently in $$$S$$$ and $$$1$$$, otherwise.
For each segment of these segment tree we will store $$$3$$$ values:
• the number of numbers from this segment, that lie in the current $$$S$$$
• the sum of numbers from this segment, that lie in the current $$$S$$$
• the sum of numbers multiplied by index from this segment, that lie in the current $$$S$$$
These values can be easily recalculated when an update in the segment tree happens.
To calculate two sums required for us we need to make the descent in the segment tree summing the segments on the prefix, where the number of numbers that lie in the current $$$S$$$ is equal to $$$k$$$.
In total, we get the $$$O((n+q) \log^2{(n+q)})$$$ solution, because we make the binary search and use queries to the segment tree inside it.