Dynamic Nonogram

Let $K$ be the current sequence length and let $S$ be the sum of its elements. If $K=0$, the answer is $0$.

For $K \ge 1$, the minimum width required by all components and the mandatory single uncolored cells between them is

$$L=S+K-1.$$

A valid coloring exists, so $L \le W$. Define the number of extra uncolored cells as

$$D=W-L.$$

Let $p_i$ be the starting cell of component $i$ when every component is packed as far left as possible. When everything is packed as far right as possible, every component starts exactly $D$ cells later, so component $i$ starts at $p_i+D$.

The cells covered by component $i$ in every valid coloring are exactly the overlap of these two intervals. Its size is

$$\max(0,A_i-D).$$

No cell outside these intervals is forced. Let $j$ be the number of left-packed components that end before such a cell. Place all $D$ extra uncolored cells in the gap between components $j$ and $j+1$. The first $j$ components are then left-packed and the remaining components are right-packed. The cases $j=0$ and $j=K$ mean the outer gaps before the first component and after the last component. In this coloring, the cell is uncolored.

Therefore, the answer is

$$\sum_{i=1}^{K}\max(0,A_i-D) = \sum_{A_i>D}A_i-D\cdot \#\{i:A_i>D\}.$$

The insertion position does not affect this formula. We only need the number of current values, their sum, and their frequency distribution.

Collect every $X$ appearing in a type-$1$ query and coordinate-compress them. Maintain two Fenwick trees over the compressed values:

• the current frequency of each value;
• the current sum contributed by each value.

An insertion or deletion updates one position in both trees. An upper_bound and two suffix queries give the count and sum of all values greater than $D$.

Each query takes $O(\log Q)$ time. The total time complexity is $O(Q\log Q)$ and the memory complexity is $O(Q)$.