P5294 [HNOI2019] Sequence

HNOI2019 day2t3

Given a sequence $A_1,A_2,\dots,A_n$ of length $n$, and $m$ operations. Each operation changes some $A_i$ to $k$. Before the first change and after each change, you need to find a **non-decreasing** sequence $B_1,B_2,\dots,B_n$ of the same length $n$, such that $\sum\limits_{i=1}^n (A_i-B_i)^2$ is minimized, and output this minimum value. Note that the effect of each operation is independent, i.e. each operation only affects the current query. To avoid precision issues, we guarantee that this minimum value is a fraction, i.e. it can be written as $\dfrac{x}{y}$ where $x$ and $y$ are non-negative integers. Then you should output $(x \times y^{P-2} \bmod P)$, which represents $\dfrac{x}{y}$ under modulo arithmetic. Here $P=998244353$ is a large prime.

The first line contains two non-negative integers $n,m$, representing the sequence length and the number of operations. The second line contains $n$ positive integers separated by spaces, representing $A_1\sim A_n$. The next $m$ lines each contain two positive integers $i,k$, meaning to change $A_i$ to $k$.

Output $m+1$ lines, each containing one integer. The $i$-th line should output the answer after the $(i-1)$-th change. In particular, the first line should be the answer for the initial state.

### Sample Explanation For the first query, an optimal sequence $B$ is $\{5, 5, 5, 5, 5\}$. For the second query, an optimal sequence $B$ is $\{1, 2, 4, 5, 5\}$. For the third query, an optimal sequence $B$ is $\{3, 3, 4, 5, 5\}$. For the fourth query, an optimal sequence $B$ is $\{5, 5, 5, 6, 6\}$. The sample is a special case where there exists an optimal solution with all $B_i$ being integers. ### Constraints and Notes For the first $10\%$ of the testdata, it is guaranteed that $n,m\le 10$, $k,A_i\le 10^3$, and there exists an optimal solution with all $B_i$ being integers. For the first $30\%$ of the testdata, it is guaranteed that $n,m\le 100$. For another $20\%$ of the testdata, it is guaranteed that $m = 0$. For another $20\%$ of the testdata, it is guaranteed that $n,m \le 3 \times 10^4$. For all testdata, it is guaranteed that $3 \le n \le 10^5$, $0 \le m \le 10^5$, $1 \le k, A_i \le 10^9$. Translated by ChatGPT 5