P15732 [JAG 2024 Summer Camp #2] Do Make Segment Tree

Given an integer sequence $B = (B_1, B_2, \ldots, B_{2^N - 1})$ of length $2^N - 1$, define $f(B)$ as follows: - $f(B)$ is the minimum number of operations required to make the following condition true: - Operation: Choose one integer $i$ such that $1 \leq i \leq 2^N - 1$, and either increase $B_i$ by $1$ or decrease $B_i$ by $1$. - Condition: For all $i$ where $1 \leq i \leq 2^{N-1} - 1$, the condition $B_i = B_{2i} + B_{2i+1}$ should be satisfied. You are given a sequence $A = (A_1, A_2, \ldots, A_{2^N - 1})$ of length $2^N - 1$. Process $Q$ queries. For each query $i$ (where $1 \leq i \leq Q$): - Given integers $x_i$ and $v_i$, update $A_{x_i}$ to $v_i$ and then output $f(A)$.

The input is given in the following format: $$ \begin{aligned} &N \\ &A_1 \ A_2 \ \ldots \ A_{2^N - 1} \\ &Q \\ &x_1 \ v_1 \\ &x_2 \ v_2 \\ &\vdots \\ &x_Q \ v_Q \end{aligned} $$ - $2 \leq N \leq 18$ - $1 \leq Q \leq 100,000$ - $-10^9 \leq A_i \leq 10^9$ - $1 \leq x_i \leq 2^N - 1$ - $-10^9 \leq v_i \leq 10^9$ - All input values are integers.

Output $Q$ lines. On the $i$-th line, output the answer for the $i$-th query.